20111221, 02:12  #1 
"Vincent"
Apr 2010
Over the rainbow
2×3^{2}×149 Posts 
MillerRabin 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 MillerRabin test to enter the list? lowest satisfing number is x=5 => 5*3*2=30 5,73,1321... Last fiddled with by firejuggler on 20111221 at 02:37 
20111221, 02:32  #2 
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 RabinMiller 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 RabinMiller tests with fixed bases, or whether it's possible to be more clever than exhaustive search in trying to do so.

20111221, 03:29  #3 
"Vincent"
Apr 2010
Over the rainbow
2×3^{2}×149 Posts 
my preceding formula was messy, therefore
8x^{3}10x^{2}+3x (as in x*(2x1)*(2*(2x1)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>2x1>4x3 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 20111221 at 03:41 
20111221, 04:50  #4  
Aug 2006
3·1,993 Posts 
Quote:
There may be yet more advanced techniques in, e.g., Zhang & Tang. Finding BPSWpseudoprimes is harder. Grantham has a list which he believes (plausibly) to contain such a pseudoprime amongst its products, see Sloane's A018188. 

20111221, 05:52  #5 
"Vincent"
Apr 2010
Over the rainbow
2·3^{2}·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?

20111221, 15:17  #6  
Einyen
Dec 2003
Denmark
31·103 Posts 
http://mathworld.wolfram.com/RabinM...primeTest.html
Quote:
http://www.ma.iup.edu/MAA/proceedings/vol1/higgins.pdf In section 4.2 they find the highest fraction of nonwitnesses 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 nonwitnesses is (p1)*(q1)/4. Last fiddled with by ATH on 20111221 at 15:18 

20111222, 05:57  #7  
Aug 2006
5979_{10} Posts 
Quote:
firejuggler: See https://oeis.org/A129521 https://oeis.org/A071294 https://oeis.org/A141768 for more information. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Probabilistic primality tests faster than Miller Rabin?  mathPuzzles  Math  14  20170327 04:00 
Number of RabinMiller NonWitnesses  ATH  Math  0  20110730 16:42 
MillerRabin Strong Probable Prime Test (SPRP)  fenderbender  Miscellaneous Math  22  20101111 01:04 
SelfTest Questions  C0C0as.  PrimeNet  8  20041025 03:26 
Why no RabinMiller Tests ?  Axel Fox  Math  13  20040628 16:07 