Posted by Jason Polak on 13. May 2018 · Write a comment · Categories: number-theory

We've been talking about the Miller-Rabin randomized primality test, which is one of the easiest to implement and most effective tests that, given a number, will either prove it to be composite or state that it is most likely prime. As good as it is for practical applications, the Miller-Rabin test leaves something to be desired.

If you need primes for cryptographic applications, Miller-Rabin practically perfect. But what if you want to generate super large primes and state for sure that the numbers you are generating really are primes?

The Lucas test is a fast test that can prove a number prime. Here it is:

Theorem (Lucas Test). Let $a$ and $n\gt 1$ be integers. If $a^{n-1}\equiv 1\pmod{n}$ and $a^{(n-1)/q}\not\equiv 1\pmod{n}$ for every prime factor $q\mid n-1$ then $n$ is prime.

The proof is quite simple: the congruences that $a$ satisfy show that $a$ generate the multiplicative group $\mathbb{Z}/n^\times$. Therefore, $n-1\mid |\mathbb{Z}/n^\times| = \varphi(n)$. However, if $n$ were composite then $\varphi(n) \lt n-1$, which contradicts $n-1\mid\varphi(n)$. Therefore, $n$ is prime.

Of course, the Lucas test only works well if you can quickly factor $n-1$. But if you're only after generating super-large primes, then you might as well choose $n-1$ already factored. For example, $2\cdot 3^i + 1$ are the kind of numbers we're after.

The other problem is the base $a$. Not all bases $a$ will satisfy the conclusion of the theorem: you need to pick a good one. So, we choose it at random. If we do so, and if $n$ is prime, then the expected number of random bases we will have to go through before finding one that works $2\log(\log(n))$. For a thousand digit number, this turns out to be around 15. Of course, it's possible that there are primes with few bases. After all, there are infinitely many natural numbers waiting to surprise us. No matter: if we stumble upon a stubborn prime, move on and try another.

Let's illustrate the Lucas test with an example:
$$n = 2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13^{628}+1.$$
I got this number by using Miller-Rabin, searching through numbers with the exponent on 13 varying. So, I'm confident that this number is prime. But let's say I want to prove $n$ prime. We know the prime factors of $n-1$, so it's a prime candidate for the Lucas test.

I mentioned we should try random bases, but it's a good idea to try a few small ones first, and then random ones, since small bases are more computationally efficient. So let's try $a = 3$. Indeed,
$$3^{n-1}\equiv 1\pmod{n}.$$
Given this, we now verify that none of the numbers $3^k$ for $k=(n-1)/q$ and $q=2,3,5,7,11,13$ are congruent to one modulo $n$. Of course, in practice, you would just write a computer program to check this, but for illustration purposes let us show the intermediate calculations. Let's start with $3^{(n-1)/2}$. It's congruent to the following number modulo $n$:

8318350746013717657371101791669698723492557612231239951230069589435294343740212
8875662278359433833018047614376928528294731754557245777771804193585972846825310
6102838669173899314710751584363087382614958901782841512467981631815660784370475
3749484472011639743444918490369286646571074427804878487857811741019684858951408
4039383765355041391405501062855817583915042648685999998178660437579457761583412
1646722318640127482454240532315399732045199407605904462870077937747622874620626
7681890356016952166202026594916706757926112919083072667680417633421142362723493
3176889083922167982127813489051624563711843547088866859227410183930936473137108
80177761226779699860649686814934250270001534942700771917496200263393510

Actually, this is just $-1$. Not surprising, as this is the first step of the Miller-Rabin test.

Now let's try $3^{(n-1)/3}$:

43000155610494087703016494039635987047290496061738153772986344532472776406686309
81975952098283693009130296557100151229940852516786513631816888669582279130084015
93263716356142022488677727252466371442306607571125192804801194698194504704587073
39356960485456312203014468210328086648175878250350676002787098889081692023303631
82187013032357956056497177887093113079935686450331023441231618627336946796063469
42042191913166385988795450962781921896283428318111755852426220529700659422240233
07110756599831079782497230393859209825313889067121483879425439831596516954956938
04698447961396251092396984435563713927060084479142192943483335543500125516401099
993029439150134962925633782232313830547554305197742892972566179

What about $3^{(n-1)/5}$?

72228626770744390165072243431219869681284726270152399420672766298854933288241857
83527234601862687574488897559689729397304160397511126665260182346062605772183188
17352509786548540707420932389358437214173834839323004273596388307597531492186434
98251823640118709179146489856986805579767586291767176228416641466983599258673953
63252061238894755592137115486404112211109467477006342215340169851149271821127046
16162405951312259435086445299141483130104757432139131872071708824296792345925495
14984533292582294466576984912546599746659263141694732895221091366512710571927163
74624570775711768260503286605689260182402233594044961937040352358040263366652570
4341102573567510355318292403536352874472134965483072673096364

And $3^{(n-1)/7}$:

51942257732804090681268678635288402840871570341089686554092171713931151456668233
25105424896772447784585085290034032901877311958758138731748185723522402932884642
25029017463840259556094910316529053419135768526989929497525518000720559592667238
65732261001351888399723426661079764501468654892702244154028402934805114789864040
78584095185519437607340598823743149835961752292126606433324969231037334099164560
50176875397262307398999839025561961511256614238554247837933074928834781255350129
45988595961698775636194895227286366468682087633057072017039029373465564480069406
88595590179129964028140668501953911873181731798616776989289700163811255866427785
76006693057018707306590663443532186169929133390406161809337995

And $3^{(n-1)/11}$:

18425931782737546342652258977585152055317394035793485204824887779373135972891485
90298173308985646605824346265907412409760064869313716629353736657745310011941748
63848775042413795662335170494035687863420117106812369621618037037921462038826958
10392131901775535004336880940428266481036356509642388592297023107618947233738967
38482216603319848149176915674015086065238771632157199408716049720805066606769062
61823297462898086076067826139635644889206284096075561447349391773159101503532947
19093007484372769032047882509685097277370748012299424008919345350953444374638855
39903355885766265333731358057256592148429686282512227297892730746702714819226346
369475386967725597877907995685127605953113740936796477035716773

And finally $3^{(n-1)/13}$:

478247882130325634341065072564804420562293506900169053048390649605720168035373651
812791407581402164631079059700938340843259402629930600849589948658963289073830286
054516364180125836052592564438991171827697109347812504183506648542942173002765230
003085797968393186357690395244530302334627049602949738671901803932042516532149367
555870421938448736728738944334528704284021175122938342875548807970650170162733301
918127881755855380075333930740895369397711993686702136276733106921269681841586005
520341313380230872792683886175700150786961047672255941997335305340934022957658214
622797995616666767853500657018263449313165189065174273389766209888508573980673889
3692209097549524168030369901380868318339495517119351884

So by the Lucas test, we have proved $n$ to be prime. Written out:

83183507460137176573711017916696987234925576122312399512300695894352943437402128
87566227835943383301804761437692852829473175455724577777180419358597284682531061
02838669173899314710751584363087382614958901782841512467981631815660784370475374
94844720116397434449184903692866465710744278048784878578117410196848589514084039
38376535504139140550106285581758391504264868599999817866043757945776158341216467
22318640127482454240532315399732045199407605904462870077937747622874620626768189
03560169521662020265949167067579261129190830726676804176334211423627234933176889
08392216798212781348905162456371184354708886685922741018393093647313710880177761
226779699860649686814934250270001534942700771917496200263393511

Of course, you don't want to use these special form numbers for cryptographic purposes! In fact, primes $n$ where $n-1$ has a bunch of small factors rapidly speeds up computations of discrete logarithms modulo $n$. Not good for secrets!

Leave a Reply

Your email address will not be published. Required fields are marked *