mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2011-12-21, 02:12   #1
firejuggler
 
firejuggler's Avatar
 
"Vincent"
Apr 2010
Over the rainbow

2×32×149 Posts
Default 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
firejuggler is offline   Reply With Quote
Old 2011-12-21, 02:32   #2
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3·1,181 Posts
Default

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.
jasonp is offline   Reply With Quote
Old 2011-12-21, 03:29   #3
firejuggler
 
firejuggler's Avatar
 
"Vincent"
Apr 2010
Over the rainbow

2×32×149 Posts
Default

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
firejuggler is offline   Reply With Quote
Old 2011-12-21, 04:50   #4
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3·1,993 Posts
Default

Quote:
Originally Posted by jasonp View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2011-12-21, 05:52   #5
firejuggler
 
firejuggler's Avatar
 
"Vincent"
Apr 2010
Over the rainbow

2·32·149 Posts
Default

So, it is doable if the tested bases are know, but impossible with random base. It seem logical. Now, which base FactorDB use?
firejuggler is offline   Reply With Quote
Old 2011-12-21, 15:17   #6
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

31·103 Posts
Default

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
ATH is online now   Reply With Quote
Old 2011-12-22, 05:57   #7
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

597910 Posts
Default

Quote:
Originally Posted by ATH View Post
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
for more information.
CRGreathouse is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Probabilistic primality tests faster than Miller Rabin? mathPuzzles Math 14 2017-03-27 04:00
Number of Rabin-Miller Non-Witnesses ATH Math 0 2011-07-30 16:42
Miller-Rabin Strong Probable Prime Test (SPRP) fenderbender Miscellaneous Math 22 2010-11-11 01:04
Self-Test Questions C0C0as. PrimeNet 8 2004-10-25 03:26
Why no Rabin-Miller Tests ? 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

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.