Re: 12799 - RSA

All about problems in Volume 127. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Repon kumar Roy
Learning poster
Posts: 96
Joined: Tue Apr 23, 2013 12:54 pm

Re: 12799 - RSA

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

Get AC :D
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 :D
Last edited by Repon kumar Roy on Sat Oct 11, 2014 6:03 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 12799 - RSA

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

1962726
11268
276873284
98088427
413865052
228007915
352893981
11661848
30255479
2895500
404307038
439009045
53970198
428962525
58710888
22820719
66456343
8294459
103770662
227454583
61309
1291517
373422507
2114563
23399336
2360316
4980530
439325237
18755821
166652535
44835510
78128018
376883197
23069761
243133335
6650450
183336441
124425059
11305069
19200295
59044329
3170739
20072454
354284
54732639
28840600
45527274
20282067
574955254
77856203
30810440
127906601
33330135
179102980
402719242
199880903
44186085
116267066
157307691
262675930
1382310
43265946
53900185
347527051
37788959
11957109
91373695
34549935
54167720
242782865
39712342
102952751
51996310
23792159
91364520
5393508
13097021
681276
8072471
8848215
21307309
318568623
650285024
104894298
16766425
60217459
346091837
180797424
58522767
7979352
116702418
22772874
121702096
32156170
650081167
549450936
59149931
64667111
357642561
346309530
Check input and AC output for thousands of problems on uDebug!

satirmo
New poster
Posts: 3
Joined: Sat Oct 11, 2014 6:23 am

Re: 12799 - RSA

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 12799 - RSA

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.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 127 (12700-12799)”