2020-08-02, 01:44 | #1 |
Aug 2020
2·5 Posts |
Solovay Strassen Mod
In the Solovay strassen primality test we can can make the the base a=2 and another a or b such that the jacobi symbol is the opposite sign of that of the jacobi of 2 with respect to n the odd composite number which we need to determine the primality of. Please comment on the paper I attached and the algorithm in pseudo code.
Thank you, Allan |
2020-08-02, 05:54 | #2 |
Aug 2020
10_{10} Posts |
This is empirically true only so far
This is only empirically determined to be true for all base 2 Euler pseudo primes uptil 2^64-1 but the proof given is not correct as it includes circular reasoning. My stupid error in posting it up. But the algorithm described there seems to be empirically correct. If any one else could find a reasonable proof it would be good.
Sorry, Allan |
2020-08-02, 06:07 | #3 |
Aug 2020
2×5 Posts |
Attached is the code I tested it with in C. It uses GMPLIB http://gmplib.org
Compile it as : gcc -o pspf -lm -m64 -lgmp pspfactorsm.c and run : ./pspf filename.out filename,in where filename.in = psps-below-2-to-64.txt The file psps-below-2-to-64.txt is unput to the program and filename.out is the output file. The file psps-below-2-to-64.txt can be found at the following URL: http://www.cecm.sfu.ca/Pseudoprimes/ Decompress the file and use it. Thank you, Allan |
2020-08-02, 06:55 | #4 |
Aug 2020
2·5 Posts |
Soory the correct code is here. The former code has j=0. It should be j=ja;
Thank you. Allan |
2020-08-02, 17:20 | #5 |
Aug 2020
10_{10} Posts |
In the Theorem proof the error is here:
2^(n-1)==1 ( mod n) = 1 (mod p) as p | n b^(n-1)==1( mod n) == 1 (mod p) as p | n Subtracting the two equivalences gives: 2^(n-1)==b^(n-1) ( mod p) Taking the square roots of both sides gives: 2((n-1)/2)==+/- b^((n-1)/2)( mod p) and not 2^((n-1)/2) == b^((n-1)/2) (mod p) as claimed in the proof. |
Thread Tools | |
Similar Threads | ||||
Thread | Thread Starter | Forum | Replies | Last Post |
Karatsuba algorithm relation to Matrix Multiplication (Strassen Algorithm)? | neomacdev | Computer Science & Computational Number Theory | 1 | 2019-07-30 01:40 |
Schönhage-Strassen Algorithm Paper | flouran | Math | 8 | 2009-05-23 23:52 |
Augment Schoenhage-Strassen with an FGT? | __HRB__ | Programming | 4 | 2009-03-02 17:34 |