mersenneforum.org Miller-Rabin test questions
 Register FAQ Search Today's Posts Mark Forums Read

 2011-12-21, 02:12 #1 firejuggler     "Vincent" Apr 2010 Over the rainbow 2×32×149 Posts Miller-Rabin test questions Looking at http://factordb.com/prooffailed.php it seems that most of the 'failed' prp are of the form x*((x+1)/2 ) (x , (x+1)/2 being prime) Would it be possible to *construct* a composite such as x*((x+1)/2)*(((x+1)/2)+1)/2) that fail enough Miller-Rabin test to enter the list? lowest satisfing number is x=5 => 5*3*2=30 5,73,1321... Last fiddled with by firejuggler on 2011-12-21 at 02:37
 2011-12-21, 02:32 #2 jasonp Tribal Bullet     Oct 2004 3·1,181 Posts You can show that it's impossible to construct an input analogous to a Carmichael number, that will pass an arbitrary number of Rabin-Miller tests with randomly chosen bases. I don't know how far people have gotten in choosing an input that happens to pass a specific number of Rabin-Miller tests with fixed bases, or whether it's possible to be more clever than exhaustive search in trying to do so.
 2011-12-21, 03:29 #3 firejuggler     "Vincent" Apr 2010 Over the rainbow 2×32×149 Posts my preceding formula was messy, therefore 8x3-10x2+3x (as in x*(2x-1)*(2*(2x-1)-1)) To qualifies, the composite must have only 3 factors. Therefore, it can only end with a 1 or a 9** I made an error on my list. 2,19,79,331,499,601,619 31 does not qualifies as I consider 11^2 as 2 factors (31,61,121? nope! 11^2) 49 does not qualifies as 49 is 7^2 421 is strange, it has 2 square 421*29^2*41^2 ** x->2x-1->4x-3 1->1->1 3->5->9 so it will have a '5 ' factor 5->9->7 so it will have a '5' factor 7->3->5 so it will have a '5' factor 9->7->3 Last fiddled with by firejuggler on 2011-12-21 at 03:41
2011-12-21, 04:50   #4
CRGreathouse

Aug 2006

3·1,993 Posts

Quote:
 Originally Posted by jasonp I don't know how far people have gotten in choosing an input that happens to pass a specific number of Rabin-Miller tests with fixed bases, or whether it's possible to be more clever than exhaustive search in trying to do so.
Pretty far. For any fixed set of bases it's possible to construct a fixed set of linear polynomials such that if all members are simultaneously prime the product is a strong pseudoprime to those bases. Under Dickson's conjecture this will happen infinitely often; it's very practical for a pretty decent number of bases IIRC.

There may be yet more advanced techniques in, e.g., Zhang & Tang.

Finding BPSW-pseudoprimes is harder. Grantham has a list which he believes (plausibly) to contain such a pseudoprime amongst its products, see Sloane's A018188.

 2011-12-21, 05:52 #5 firejuggler     "Vincent" Apr 2010 Over the rainbow 2·32·149 Posts So, it is doable if the tested bases are know, but impossible with random base. It seem logical. Now, which base FactorDB use?
2011-12-21, 15:17   #6
ATH
Einyen

Dec 2003
Denmark

31·103 Posts

http://mathworld.wolfram.com/Rabin-M...primeTest.html

Quote:
 Monier (1980) and Rabin (1980) have shown that a composite number passes the test for at most 1/4 of the possible bases . If N multiple independent tests are performed on a composite number, then the probability that it passes each test is 1/4N or less.

http://www.ma.iup.edu/MAA/proceedings/vol1/higgins.pdf

In section 4.2 they find the highest fraction of non-witnesses is for numbers n=p*q, where p and q are primes of the forms p=2r+1, q=4r+1 and r is odd. The number of non-witnesses is (p-1)*(q-1)/4.

Last fiddled with by ATH on 2011-12-21 at 15:18

2011-12-22, 05:57   #7
CRGreathouse

Aug 2006

597910 Posts

Quote:
 Originally Posted by ATH In section 4.2 they find the highest fraction of non-witnesses is for numbers n=p*q, where p and q are primes of the forms p=2r+1, q=4r+1 and r is odd. The number of non-witnesses is (p-1)*(q-1)/4.
Right.

firejuggler: See
https://oeis.org/A129521
https://oeis.org/A071294
https://oeis.org/A141768

 Similar Threads Thread Thread Starter Forum Replies Last Post mathPuzzles Math 14 2017-03-27 04:00 ATH Math 0 2011-07-30 16:42 fenderbender Miscellaneous Math 22 2010-11-11 01:04 C0C0as. PrimeNet 8 2004-10-25 03:26 Axel Fox Math 13 2004-06-28 16:07

All times are UTC. The time now is 06:33.

Sat Nov 27 06:33:41 UTC 2021 up 127 days, 1:02, 0 users, load averages: 0.67, 0.94, 1.04