20110421, 11:36  #23  
Nov 2003
3×13×191 Posts 
Quote:


20110422, 11:01  #24 
Apr 2010
2·7 Posts 
:) PARI/GP can write programs in C
Code:
ifelse(n,p,k)={ my(c); if(p<k, if(n>0,print); for(i=0,n,print1(" ")); c=(p+k)>>1; print1("if(a1262["c"]<n)"); ifelse(n+1, c+1, k); for(i=0,n,print1(" ")); print1("else"); ifelse(n+1, p, c) , print(" return a1262["p"]==n;"); ); } fun(k)={ print("int test(unsigned long long n) {"); lt=eq=0; ifelse(0,1,k); print("} "); } fun(6) Code:
int test(unsigned long long n) { if(a1262[3]<n) if(a1262[5]<n) return a1262[6]==n; else if(a1262[4]<n) return a1262[5]==n; else return a1262[4]==n; else if(a1262[2]<n) return a1262[3]==n; else if(a1262[1]<n) return a1262[2]==n; else return a1262[1]==n; } only log2(2314)+1=12 tests in 2314*2 rows of programm 310 base 2 and 101 pseudoprimes below 145046817709 Last fiddled with by Xitami on 20110422 at 11:16 
20110422, 14:22  #25 
Apr 2010
2×7 Posts 

20110422, 18:27  #26 
Einyen
Dec 2003
Denmark
5·571 Posts 
The full list is here:
http://www.cecm.sfu.ca/Pseudoprimes/index2to64.html but this include all 118,968,378 Fermat base2 PRP + Miller Rabin SPRP base2. The best constant second base I found so far is 9375 where 1,147,253 (0.9643%) survives. More exotic choices does a bit better. For number n if you use base: floor(n/5)+49 then 1,092,753 survives. Base: floor(Sqrt(n))+1: 1,023,767 survives. 
20110426, 13:14  #27  
Apr 2010
2×7 Posts 
Quote:
Code:


20110427, 18:33  #28  
Jun 2003
Ottawa, Canada
1169_{10} Posts 
Quote:
Back in 2009 when David and I finished double checking the psp database, I was able to confirm there were no BPSW psp up to 2^64 with his database (assuming we did in fact enumerate all of them) and posted that here: http://gilchrist.ca/jeff/factoring/pseudoprimes.html Charles Greathouse has also confirmed no BPSW psp exist using the BPSW implementation in PARI with Jan Feitsma's database so two different implementations of BPSW have also been tried. Last fiddled with by Jeff Gilchrist on 20110427 at 18:39 

20110428, 04:03  #29 
Aug 2006
16E6_{16} Posts 
I know that many people have checked this, but I don't know which implementations of BPSW were used (though as you point out, it's at least two).

20110524, 16:57  #30 
May 2011
France
161_{10} Posts 
2^32 primes
Why are you not using an array with all the primes smaller tahnn2^32?
You have only 200 000 000 of primes so using a simple RLE the file is 200 000 000 of byte Two hours to compute the llst (i can give the file) and you can factorized 20 digits number in less than one minute. For the classic m^k mod you can use a fast algo Code:
function E_M(m, K, N: int64): int64; var b, a: int64; begin b := 1; a := m; if odd(k) then b := A; k := k shr 1; repeat A := (A * A) mod N; if odd(k) then b := (A * b) mod N; k := k shr 1; until k = 0; result := b; end; John Last fiddled with by JohnFullspeed on 20110524 at 17:00 
20110524, 18:38  #31  
Aug 2006
2·3·977 Posts 
Two hours?!? It takes PARI 11 seconds on this machine. (Technically that's "just" to 4.26e9 since this computer is running 32bit gp.)
Quote:
But primality testing is much faster than factoring! PARI only takes about 2 milliseconds to prove that a number is prime; typical composites are extremely easy to detect, taking only 20 *microseconds* by my calculations (I had to test 100,000 to get good timing!). So trial division works at that size, but we're looking for something really fast here. 

20110524, 20:51  #32 
Apr 2010
2·7 Posts 
A := (A * A) mod N;
John, how long is A*A? 
20110525, 07:32  #33 
May 2011
France
10100001_{2} Posts 
a:=a*a mod N
10000 bits if you want....
In fact you can use this mrethod for othezr problems as divisioins.. The method is: Let A and B be big positive integerss Let ? an sllower opoeraareationn A ? B = C you work on the binary representation each bit of A If te bit is 0 you make a specific code if the bit is 1 you make and other code you pass to, the Bit after unil A have bit Code:
function E_M(m, K, N: int64): int64; var b, a: int64; begin b := 1; a := m; if odd(k) then b := A; k := k shr 1; <= first bit of tha operande repeat A := (A * A) mod N; <= in all casae Bit=0 or Bit=1 if odd(k) then <= the bit is 1 b := (A * b) mod N; k := k shr 1; <+ nexT bit until k = 0; <= no new bit (end) result := b; end; Is't easy to do a faster div.... A := (A * A); <= in all casae Bit=0 or Bit=1 if odd(k) then <= the bit is 1 b := (A * b); k := k shr 1; <+ nexT bit until k = 0; <= no new bit (end) You understood that A can have 1000 bios you make 'only' 1000+5000 divmod John 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Do normal adults give themselves an allowance? (...to fast or not to fast  there is no question!)  jasong  jasong  35  20161211 00:57 
How to Check if NonMersenne Number isPrime?  FloatingPoint  Operation Billion Digits  39  20151021 02:15 
How fast is the dog?  Andi47  Puzzles  20  20090401 02:35 
I wonder how fast this is...  ixfd64  Hardware  1  20051121 21:28 
Fast way to square???  maheshexp  Math  2  20040529 01:54 