mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Closed Thread
 
Thread Tools
Old 2021-04-15, 00:12   #1
LarsNet
 
Mar 2021

23·3 Posts
Minus 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 <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 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
LarsNet is offline  
Old 2021-04-15, 02:21   #2
axn
 
axn's Avatar
 
Jun 2003

2×2,539 Posts
Default

Quote:
Originally Posted by LarsNet View Post
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.
axn is offline  
Old 2021-04-15, 02:30   #3
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

5,881 Posts
Default

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.
henryzz is online now  
Old 2021-04-15, 02:48   #4
LarsNet
 
Mar 2021

23·3 Posts
Default

Sorry, i meant 50,000,000,000. I'm working my way up to a trillion on my cpu now.
LarsNet is offline  
Old 2021-04-15, 02:50   #5
LarsNet
 
Mar 2021

110002 Posts
Default

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.
LarsNet is offline  
Old 2021-04-15, 05:25   #6
Happy5214
 
Happy5214's Avatar
 
"Alexander"
Nov 2008
The Alamo City

2·347 Posts
Default

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.
Happy5214 is offline  
Old 2021-04-15, 08:19   #7
LarsNet
 
Mar 2021

2410 Posts
Default

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
LarsNet is offline  
Old 2021-04-15, 11:39   #8
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

5·751 Posts
Default

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.
paulunderwood is offline  
Old 2021-04-15, 21:27   #9
LarsNet
 
Mar 2021

23×3 Posts
Default

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 :-)
LarsNet is offline  
Old 2021-04-16, 08:00   #10
S485122
 
S485122's Avatar
 
Sep 2006
Brussels, Belgium

1,693 Posts
Default

Quote:
Originally Posted by LarsNet View Post
...
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
S485122 is offline  
Old 2021-04-22, 00:13   #11
LarsNet
 
Mar 2021

23×3 Posts
Default

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.
LarsNet is offline  
Closed Thread

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Reproducible round off errors near end of test Runtime Error Software 21 2021-03-13 16:39
Didn't even find a useless factor of an uninteresting number! Take that! storflyt32 storflyt32 298 2018-09-27 02:36
A Theoretical (vs. Proficient/Practical) Deterministic Primality Test a1call Miscellaneous Math 194 2018-03-19 05:54
Help test 210885 - Find a new top 5000 prime! SlashDude Riesel Prime Search 121 2008-01-03 08:47
Help test 2995125705 - Find a new top 5000 prime! SlashDude Riesel Prime Search 538 2007-05-08 01:42

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


Tue Jul 27 18:42:59 UTC 2021 up 4 days, 13:11, 0 users, load averages: 2.19, 1.77, 1.73

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.