mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Miscellaneous Math (https://www.mersenneforum.org/forumdisplay.php?f=56)
-   -   I didn't find a 5 round deterministic MillerRabin Test (https://www.mersenneforum.org/showthread.php?t=26705)

 LarsNet 2021-04-15 00:12

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 [url]https://oeis.org/A001262/b001262.txt[/url] 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 <gmp.h>
#include <stdio.h>

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 zero;
mpz_t one;
mpz_t negN;
mpz_init(negN);
mpz_init_set_ui(zero, 0);
mpz_init_set_ui(one, 1);
mpz_sub(negN, zero, N);
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);
}
}
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]

[CODE]
./gmptest 2110229697309202254897383305762150945330987087513434511395506048950594976569434432057019507105035289374307720719984431280856161609820548842778454256113246763860786119268583367543952735347969627478873317341364209555365064365565504232770227619462128918701942169785585423104678142850200975026619010035331023744330713985615650556129731348659986462960062760308034462660525448390420668021248422741300646552941285862310410598374242189448623917196191138254637812716211329113836605859918549332304189053950819346551095911511755911832183789503704294770046935064469435830299623205136625543859303686699678929069468518950480476841246805908501510754550017255944080874819287974625925494008373883250410775902993163965873632474224574883242826458163446781002284368017611606202344050570737818087202137703099075773680753707346415849787963446390136517016131227807076254668461445862154978026041507116570585784569893773262639243954090283224759975513502582494002154146757110676408972377044584495342170277522887809749465855954126593100747444378301829661568735873345178089061677917127496915956539418931430313218084338374827152407795095072639044306222222695685778907958272820576498682506540189586657786292950574081739269257159839589987847266550007783514316481286222515710538845836151864127815058116482680058626451349913138908040817800742009650450811565324184631847563730941344941348929727603343965091116543702880556850922077216848669966268219928808236163268726995495688157209747596437162960244538054993785127947211290438554095851924381172697827312534174244295581184309147813790451951453564726742200569263225639113681905176376701339808868274637448606821696026703034737428319530072483125495383057919894902076566679023694181381398377144302767983385253577700652358431959604517728821603076762965129019244904679015099154368058005173028200266632883632953133017055122970338782493475762548347258351148037427739052271661340801912188203749647918379812483260399614599813650518046331670764766419886619324840045611486524123102046413946014624119568013100078163986683199814025915420877588778260860713148420321896163326473203441644820182490479899368048072263481024886708136521847014624735722333931331098969321911443978386868675912141648200500219168920887757573018380579532261231821382787339600631297820996466930957801607217549420247654458172818940238337170577825003408756362106088558651381993611741503374243481167926898332728164900189941804942580426055589622673679047058619682175301326905577843405270203660160407401675700528981573327582844330828861745574031416926871562443652858767649050943181353635950301154441954046214987718582670685455252774874198771086552440702483933126644594300464549471422237478151976561680719370424626162642534252062987911763456822609569209140676822858933588602318066530038691463577379331113471591913447226829868760176810195567325921301390329055242213842898142597360121925124635965685365925901913816717677946911762631634793638450106377437599347740569467683272089859392249351406815344105961234868327316964137925419770514177021722214309784062017826024217906664090209434553785436385765927274067126192143337589109608949427467825999057058702263715338956534536892852849984934736685814891286495169007648767081688963426768409476169071460997622740467533572971356017575900999100928776382541052696124463195981888715845688808970103527288822088031150716134784735332326775370417950625124642515148342694377095213470544739900830244879573205335578256682901821773047071352497997708791157012233232529777513203024818391621220967964874173106990772425289900446640237659116713251437567138729645677868024033209183367071421651937808005637679844370347367922676824239404492688418047080583797577102267329067247758368597488680401670673861120323439239792549053895366970423259196919428554146265587250617656401028722578111927104663315250291888502226235291264834968061065817079511872899991276288365723969841290984981957389126603952133124328219936785870274843554107325931034103072894378438818494802517594594270034007832922248742746517915210656205746338575621725899098414488628833412591266637224507533934158213117522503993423240638893845121918647788013
True
[/CODE]

 axn 2021-04-15 02:21

[QUOTE=LarsNet;575923]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 [url]https://oeis.org/A001262/b001262.txt[/url] 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.[/QUOTE]

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.

 henryzz 2021-04-15 02:30

A test that is deterministic up to 50m is not difficult to find. [url]https://miller-rabin.appspot.com/[/url] has records for this sort of thing.

 LarsNet 2021-04-15 02:48

Sorry, i meant 50,000,000,000. I'm working my way up to a trillion on my cpu now.

 LarsNet 2021-04-15 02:50

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.

 Happy5214 2021-04-15 05:25

I found a counter-example. 1469328248071876501 passes your test, but is listed on [URL="https://oeis.org/A074773/b074773.txt"]this list of numbers which are strong pseudoprimes to bases 2, 3, 5, and 7[/URL].

 LarsNet 2021-04-15 08:19

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.

 paulunderwood 2021-04-15 11:39

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.

 LarsNet 2021-04-15 21:27

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 :-)

 S485122 2021-04-16 08:00

[QUOTE=LarsNet;575984]...
Also, i like the OPs sense of humor for changing my title :-)[/QUOTE]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

 LarsNet 2021-04-22 00:13

Does anyone think my test is better than what's posted at [url]https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test#Deterministic_variants[/url] ? Mine is deterministic and algorithmic, and yes, it failed one number at [url]https://oeis.org/A074773/b074773.txt[/url] 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.

All times are UTC. The time now is 02:23.