mersenneforum.org I didn't find a 5 round deterministic MillerRabin Test
 Register FAQ Search Today's Posts Mark Forums Read

 2021-04-15, 00:12 #1 LarsNet   Mar 2021 23×3 Posts I didn't find a 5 round deterministic MillerRabin Test I think i found a 5 round deterministic MillerRabin Test. What i did was take the mod inverse of the number we are testing and create a number, let's call it "k", with it's modinverse of its 2**number.bit_length(), then subtracted 1 from that number. so basically a modinverse like this: k = pow(number, -1, 2**number.bit_length()) - 1 I then took 5 tests, [k-2, k-1, k, k+1, k+2] and use only those numbers to perform a MillerRabin Test. So far i haven't found any prime numbers that fail the test. So far i tested against https://oeis.org/A001262/b001262.txt and up to 50,000,000 ( and i'm still running it in the background, so sorry for the low number my cpu is not all that fast and i don't have a parallel c version to quickly test) and no failures yet. So with that, while i'm testing, I would like to know if any mathematicians can tell me why it couldn't work or why it should fail as so far i have found no numbers that fail that 5 round test using numbers from that mod inverse. If you know how to make a test that fails, let me know. I know this needs much more testing that's why i'm not making the claim it works 100%, i'm just showing so far i haven't been able to make it fail and do not know how to do so, so I wanted some input on what i've found so far. Maybe someone knows a test that can prove it doesn't work? I wrote this code in c to show it, now this is not as good as my python code because i'm not a c programmer, and it could be made much faster if the tests were all done in parallel because 5 tests at once should be easily doable in c, i just don't know how, but i have done it in python. Here is the code for those interested: Code: #include #include int MillerRabin(mpz_t n, mpz_t exp, mpz_t ll, mpz_t iterx) { mpz_t test; mpz_t primetest; mpz_t nminusone; mpz_t one; mpz_t two; mpz_init(test); mpz_init(primetest); mpz_init_set_ui(one, 1); mpz_init_set_ui(two, 2); mpz_init(nminusone); mpz_sub(nminusone, n, one); mpz_powm(primetest, ll, exp, n); // gmp_printf ("%Zd, %Zd\n", primetest, nminusone); if ((mpz_cmp(primetest, one) == 0) || (mpz_cmp(primetest, nminusone) == 0)) { return 1; } else { for (int i = 0; i < mpz_get_ui(iterx); i++) { mpz_powm(primetest, primetest, two, n); // gmp_printf("Primetest: %Zd\n", primetest); if (mpz_cmp(primetest, nminusone) == 0) { return 1; } if (mpz_cmp(primetest, one) == 0) { return 0; } } } return 0; } void fffs(mpz_t N, mpz_t iterx) { mpz_t xx; mpz_t answer; mpz_t zero; mpz_t one; mpz_t negN; mpz_init(negN); mpz_init(answer); mpz_init_set_ui(zero, 0); mpz_init_set_ui(one, 1); mpz_sub(negN, zero, N); mpz_and(answer, N, negN); mpz_init_set_ui(xx, mpz_sizeinbase(answer, 2)); mpz_sub(iterx, xx, one); } int sfactorint_isprime(mpz_t n) { mpz_t testforeven; int result; mpz_t ll; mpz_t llarray[4]; mpz_t z; mpz_t iterx; mpz_t nminusone; mpz_t zero; mpz_t one; mpz_t negone; mpz_t three; mpz_t exp; mpz_init(exp); mpz_init_set_ui(negone, -1); mpz_init_set_ui(zero, 0); mpz_init_set_ui(one, 1); mpz_init_set_ui(three, 3); mpz_init(iterx); mpz_init(nminusone); mpz_init(testforeven); mpz_sub(nminusone, n, one); int x; mpz_t minv; mpz_t two; mpz_init(ll); mpz_init_set_ui(two, 2); mpz_mod(testforeven, n, two); if (mpz_cmp(testforeven, zero) == 0 || mpz_cmp(n, two) < 0) { return 0; } mpz_init_set_ui(minv, -1); x = mpz_sizeinbase(n, 2); // printf("%d\n", x); mpz_t x_mpz; mpz_init_set_ui(x_mpz, x); mpz_t p2; mpz_init(p2); mpz_pow_ui(p2, two, x); // gmp_printf("%Zd\n", p2); mpz_powm(ll, n, minv, p2); mpz_sub(ll, ll, three); // gmp_printf("%Zd\n", ll); fffs(nminusone, iterx); // gmp_printf("Iterx: %Zd\n", iterx); mp_bitcnt_t iterxbc; mpz_tdiv_q_2exp(exp, n, mpz_get_ui(iterx)); // gmp_printf("%Zd\n", exp); int prime = 0; for (int i = 0; i<5; i++) { if (mpz_cmp(ll, nminusone) > 0) { mpz_mod(ll, ll, n); } if (mpz_cmp(ll, one) > 0) { result = MillerRabin(n, exp, ll, iterx); if (result == 0) { return 0; } //printf("%d\n", result); } mpz_add(ll, ll, one); } return 1; } int main( int argc, char *argv[] ) { mpz_t p; mpz_t pp; int result; // printf("\n%s\n", argv[1]); mpz_init(p); mpz_set_str(p, argv[1], 10); //gmp_printf("%Zd\n", p); result = sfactorint_isprime(p); if (result == 0) { printf("False\n"); } else { printf("True\n"); } } Code: ./gmptest 2110229697309202254897383305762150945330987087513434511395506048950594976569434432057019507105035289374307720719984431280856161609820548842778454256113246763860786119268583367543952735347969627478873317341364209555365064365565504232770227619462128918701942169785585423104678142850200975026619010035331023744330713985615650556129731348659986462960062760308034462660525448390420668021248422741300646552941285862310410598374242189448623917196191138254637812716211329113836605859918549332304189053950819346551095911511755911832183789503704294770046935064469435830299623205136625543859303686699678929069468518950480476841246805908501510754550017255944080874819287974625925494008373883250410775902993163965873632474224574883242826458163446781002284368017611606202344050570737818087202137703099075773680753707346415849787963446390136517016131227807076254668461445862154978026041507116570585784569893773262639243954090283224759975513502582494002154146757110676408972377044584495342170277522887809749465855954126593100747444378301829661568735873345178089061677917127496915956539418931430313218084338374827152407795095072639044306222222695685778907958272820576498682506540189586657786292950574081739269257159839589987847266550007783514316481286222515710538845836151864127815058116482680058626451349913138908040817800742009650450811565324184631847563730941344941348929727603343965091116543702880556850922077216848669966268219928808236163268726995495688157209747596437162960244538054993785127947211290438554095851924381172697827312534174244295581184309147813790451951453564726742200569263225639113681905176376701339808868274637448606821696026703034737428319530072483125495383057919894902076566679023694181381398377144302767983385253577700652358431959604517728821603076762965129019244904679015099154368058005173028200266632883632953133017055122970338782493475762548347258351148037427739052271661340801912188203749647918379812483260399614599813650518046331670764766419886619324840045611486524123102046413946014624119568013100078163986683199814025915420877588778260860713148420321896163326473203441644820182490479899368048072263481024886708136521847014624735722333931331098969321911443978386868675912141648200500219168920887757573018380579532261231821382787339600631297820996466930957801607217549420247654458172818940238337170577825003408756362106088558651381993611741503374243481167926898332728164900189941804942580426055589622673679047058619682175301326905577843405270203660160407401675700528981573327582844330828861745574031416926871562443652858767649050943181353635950301154441954046214987718582670685455252774874198771086552440702483933126644594300464549471422237478151976561680719370424626162642534252062987911763456822609569209140676822858933588602318066530038691463577379331113471591913447226829868760176810195567325921301390329055242213842898142597360121925124635965685365925901913816717677946911762631634793638450106377437599347740569467683272089859392249351406815344105961234868327316964137925419770514177021722214309784062017826024217906664090209434553785436385765927274067126192143337589109608949427467825999057058702263715338956534536892852849984934736685814891286495169007648767081688963426768409476169071460997622740467533572971356017575900999100928776382541052696124463195981888715845688808970103527288822088031150716134784735332326775370417950625124642515148342694377095213470544739900830244879573205335578256682901821773047071352497997708791157012233232529777513203024818391621220967964874173106990772425289900446640237659116713251437567138729645677868024033209183367071421651937808005637679844370347367922676824239404492688418047080583797577102267329067247758368597488680401670673861120323439239792549053895366970423259196919428554146265587250617656401028722578111927104663315250291888502226235291264834968061065817079511872899991276288365723969841290984981957389126603952133124328219936785870274843554107325931034103072894378438818494802517594594270034007832922248742746517915210656205746338575621725899098414488628833412591266637224507533934158213117522503993423240638893845121918647788013 True
2021-04-15, 02:21   #2
axn

Jun 2003

496310 Posts

Quote:
 Originally Posted by LarsNet I then took 5 tests, [k-2, k-1, k, k+1, k+2] and use only those numbers to perform a MillerRabin Test. So far i haven't found any prime numbers that fail the test. So far i tested against https://oeis.org/A001262/b001262.txt and up to 50,000,000 ( and i'm still running it in the background, so sorry for the low number my cpu is not all that fast and i don't have a parallel c version to quickly test) and no failures yet.
This might or might not work. If someone could find a counterexample, that would obviously disprove your claim. Yet, doing test after test of successful confirmation will not get you any closer to actually proving that this is deterministic. You'll need to offer a mathematical proof that this works -- I doubt that you have such a proof. Until such time, no one will treat it as a deterministic test.

 2021-04-15, 02:30 #3 henryzz Just call me Henry     "David" Sep 2007 Cambridge (GMT/BST) 587010 Posts A test that is deterministic up to 50m is not difficult to find. https://miller-rabin.appspot.com/ has records for this sort of thing.
 2021-04-15, 02:48 #4 LarsNet   Mar 2021 23·3 Posts Sorry, i meant 50,000,000,000. I'm working my way up to a trillion on my cpu now.
 2021-04-15, 02:50 #5 LarsNet   Mar 2021 308 Posts Your correct, i'm an amateur mathematician at best, but i will take a look at writing a proof with my limited knowledge if no one finds any glaring errors. At least then i would know why or why not this works so well in my limited, but expanding testing. I do study a lot of math on primes.
 2021-04-15, 05:25 #6 Happy5214     "Alexander" Nov 2008 The Alamo City 60510 Posts I found a counter-example. 1469328248071876501 passes your test, but is listed on this list of numbers which are strong pseudoprimes to bases 2, 3, 5, and 7.
 2021-04-15, 08:19 #7 LarsNet   Mar 2021 23×3 Posts Ok, that's a good learning experience for me. to pass the test for all those numbers i had to have [k-3, k-2, k-1, k, k+1, k+2, k+3] which means my k array has to expand as numbers get larger. that's good to know. thanks With that, I don't know if this is worth pursuing anymore. I'm not sure at what bit boundries to increase the k size or if it's even interesting to figure out how to do so But at least it was interesting to know i could pass the test for those number by expanding from 5 tests to 7 tests. Last fiddled with by LarsNet on 2021-04-15 at 08:28
 2021-04-15, 11:39 #8 paulunderwood     Sep 2002 Database er0rr 2·11·167 Posts No matter how many -- a reasonable number -- MR tests you do there will be counterexamples. 1+1..+1+1 selfridges is a poor test and cryptographically weak. This is one of the reasons why GMP now implements BPSW which has one Lucas component.
 2021-04-15, 21:27 #9 LarsNet   Mar 2021 23·3 Posts Sorry i didn't find what i thought, and thanks for helping me find what this was. I no longer have to waste cycles on proving it whether it's true or not due to your help. Also, i like the OPs sense of humor for changing my title :-)
2021-04-16, 08:00   #10
S485122

Sep 2006
Brussels, Belgium

110100001102 Posts

Quote:
 Originally Posted by LarsNet ... Also, i like the OPs sense of humor for changing my title :-)
OP : Original Poster

Moderators : Those whose names are in red. Some may be moderators for a sub-forum only, others for the whole forum. They are the ones who change titles (and perform a lot of other tasks : clean up junk posts, keep discussions within the accepted bounds of the subforum, ban users, close threads... They have access to the "David Hasselhoff" sub-forum !)

Jacob

 2021-04-22, 00:13 #11 LarsNet   Mar 2021 23·3 Posts Does anyone think my test is better than what's posted at https://en.wikipedia.org/wiki/Miller...istic_variants ? Mine is deterministic and algorithmic, and yes, it failed one number at https://oeis.org/A074773/b074773.txt but changing from [k-2, k-1, k, k+1, k+2] to [k+3, k-2, k-1, k, k+1, k+2, k+3] it passes them all. Are there bigger number lists than oeis A074773 to test against, and does anyone think it's interesting or worthwhile for me to pursue further in comparison to the Wikipedia deterministic Miller Rabin test? Yes, i know that BPSW is the best test, but i'm just wondering in comparison to the Wikipedia entry if I've found anything interesting and worth pursuing further, and i'd rather not waste too many cycles on this if no one finds this interesting or possibly a better avenue than posted at Wikipedia.

 Similar Threads Thread Thread Starter Forum Replies Last Post Runtime Error Software 21 2021-03-13 16:39 storflyt32 storflyt32 298 2018-09-27 02:36 a1call Miscellaneous Math 194 2018-03-19 05:54 SlashDude Riesel Prime Search 121 2008-01-03 08:47 SlashDude Riesel Prime Search 538 2007-05-08 01:42

All times are UTC. The time now is 11:18.

Fri May 14 11:18:29 UTC 2021 up 36 days, 5:59, 0 users, load averages: 2.42, 1.75, 1.65