Re: 12799 - RSA

Repon kumar Roy · Post by **Repon kumar Roy** » Wed Oct 08, 2014 8:26 am

Get AC

Algo :
I assumed n = pq , that n has only two odd prime divisor
Generate Prime with sieve , Find a divisor of n , then p
Then extended euclid theorem to find d , then used big mod

HappY Debugging

brianfry713 · Post by **brianfry713** » Wed Oct 08, 2014 9:46 pm

Input:

Code: Select all

39774487 29737457 17739355
136141 80237 75747
380534411 166257089 284524500
161960131 16117573 142214312
559050361 453654059 15976468
281011603 31961135 257033638
431693443 199459979 401476639
174487321 42509429 34111625
87393143 78134197 79303453
5261987 1151935 4787705
520728983 499680761 366165504
752474659 251527369 268636560
549225563 125042453 261900138
445733539 29073491 398535979
208705171 170942717 7971651
64998517 16034323 34207626
100039553 4743415 26629352
9968311 8071197 3222763
194114681 155338181 44031662
805686731 678118823 373609383
165251 128227 157850
64077851 44343439 36206763
417160259 91232369 144350904
4025767 1903197 194740
30285623 795497 27371405
4048183 2102129 727611
50716361 49492129 10389955
701585173 265671199 524816686
24570829 7999133 10574846
582063913 238586911 359138253
192547013 166819483 187024761
78150791 12192709 6183251
525759649 51904151 140635091
66716801 48783593 56164489
434333803 224412241 426463100
11593123 887707 6280318
255567163 225995801 177633496
551000591 230308303 115647007
23568361 18191837 910085
20550227 4523657 9314260
71243593 35731469 45749759
5733139 202217 1389432
41707079 26553433 17201004
567823 452243 273343
217416613 83105081 116298888
78875609 13806277 23276545
79865041 37811531 34433171
89334293 32091883 70402666
644014523 576154711 595207057
521306959 19063983 289525781
52386307 48624149 39469287
316864313 204646669 174357084
156676909 61098055 48062665
570250073 260713181 505807284
549829381 323153421 41101098
208084853 121709351 171099346
161167987 114765177 30071210
227877427 137455391 88812541
600968597 495826921 587417851
280244873 133708261 130148559
6233783 6219403 5179292
89525641 30239747 80761978
58020121 25858027 39762333
351624541 339953223 267430699
115396453 2673313 17630916
14016973 12438625 6839784
297432257 172609727 276310677
127019707 113065693 69119965
80665349 18312569 45614415
274413553 267947633 162773251
66608137 18730611 39531310
208653169 181228493 9121003
610453859 39888821 153062600
96187199 36311449 35915542
642846983 465853985 126237219
19148891 16189643 2832060
15147173 8808733 7983549
78542011 24742275 20882809
13610689 1085663 7725517
17487139 16465879 14966494
74756029 74264981 41015180
376298393 320660167 196381313
818844679 250603763 103633475
336847493 128628763 5248272
28568467 11803395 10051684
79000949 51328759 72136778
401601479 207002581 221123528
204269731 131772691 195629913
411482549 99889427 246808717
31290211 6686881 29972572
624337999 42943855 73742688
257383393 36689633 33337540
194584211 126239509 151811980
133827913 69364295 75054906
720608297 3122771 310169202
570293489 411961453 177607568
199064123 26691563 137459737
120653261 24885133 83257999
556053331 520550463 131830948
449980133 182014141 33495339

AC output:

Code: Select all

satirmo · Post by **satirmo** » Sat Oct 11, 2014 6:28 am

I have passed all of Brianfry's test cases, but my code is still getting the Wrong Answer verdict.

Are there any corner cases? I basically find N's two divisors, calculate the phi( N ), and find e's modular inverse with respect to phi( N ) using Extended Euclid. After that we are able to simple use modular exponentiation.

Code: Select all

#include "bits/stdc++.h"

#define maxn 32000
using namespace std;

typedef long long ll;

ll arr[ 2 ];
vector < ll > prime;
bitset < maxn > bit;

void sieve()
{
  for( int i = 2; i < maxn; i++ )
    if( ! bit[ i ] )
    {
      for( int j = i*i; j < maxn; j += i )
        bit[ j ] = true;
      prime.push_back( i );
    }
}

ll mod_inv( ll a, ll m )
{
  if( m == 1 )
    return 1;
  ll x = 0, y = 1;
  ll r = m, s = a % m;
  while( s )
  {
    ll q = r / s;
    ll t = y;
    y = x - q * y, x = t;
    t = s;
    s = r - q * s, r = t;
  }
  if( r > 1 )
    return -1;
  if( x < 0 )
    x += m;
  return x;
}

ll exp_mod( ll b, ll p, ll m )
{
  ll ret = 1LL;
  while( p > 0 )
  {
    if( p & 1 )
    {
      ret *= b;
      ret %= m;
    }
    b *= b;
    b %= m;
    p >>= 1;
  }
  return ret;
}


main()
{
  sieve();
  
  ll n, e, c;
  while( cin >> n >> e >> c )
  {
    int t = 0, tmp = n;
    for( int i = 0; i < prime.size(); i++ )
      while( tmp % prime[ i ] == 0 )
        arr[ t++ ] = prime[ i ], tmp /= prime[ i ];
  
    ll phi = ( arr[ 0 ] - 1LL ) * ( arr[ 1 ] - 1LL );
  
    ll d = mod_inv( e, phi );
  
    ll m = exp_mod( c, d, n );
    printf( "%I64d\n", m );
  }
}

brianfry713 · Post by **brianfry713** » Sat Oct 11, 2014 7:14 am

Use %lld instead of %I64d, p or q might be bigger than 32000. Find the first prime factor p, then q = n / p.