Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The Miller–Rabin (or Rabin-Miller) primality test is an algorithm that determines whether a given number is prime.

Is it possible to construct a number that will pass an arbitrary number of Miller-Rabin and Rabin-Miller test rounds?

This Generating Strong Prime Numbers Report paper has test numbers that pass 20 rounds of MR.

I would like a general method test number that can pass $n$ (for example, $n = 50$) rounds, if such a thing is possible.

Thanks for any insights.

share|improve this question
2  
such things are not generally known with any degree of specificity, otherwise the information could be incorporated into an improved test. –  Will Jagy Jan 18 '13 at 0:12
    
+1 I like this question. –  amWhy May 21 '13 at 0:16
    
+1 Likewise, I am too –  Babak S. May 22 '13 at 5:00
    
+1 So do I. However, in its actual form, the answer is simple: Any prime will do. You might want to ask for a composite number ;) –  Tomas Aug 11 '13 at 21:48

4 Answers 4

The question is a bit misguided. Miller Rabin uses a combination of Fermat's Little Theorem and Chinese Division Theorem to promise that a false prime for any number is not returned with a probability of more than 25%. So for any given composite number at least 3 tries out of 4 with a single test MR will report it as composite. http://rosettacode.org/wiki/Talk:Carmichael_3_strong_pseudoprimes,_or_Miller_Rabin%27s_nemesis#Analysis examines the behaviour for a range of numbers. Note that for 703 (19*37) MR will report it as possibly prime 22.86% of the time with 1 try. So with 10 tries it will report it incorrectly 1 in a million times. See http://rosettacode.org/wiki/Talk:Miller-Rabin_primality_test. Note that for most composites the probability is much less than 25%. So the answer is that finding a number which meets your requirement is simple. Any prime will do, no composite will. I think that the confusion is that the paper suggests that these seven numbers are composite. Dong is wong they are not. The chances of finding an MR pseudoprime is the same as finding a left over plesiosaur in Loch Ness, they are both mythical. Dong didn't find 7 for his class project, these numbers are prime.

share|improve this answer
    
Nigel, you have accidentally created two accounts, which is why you were not able to edit your post directly. Here is the process to merge your accounts: From any page footer → 'contact us' » 'Merge user profiles' –  Zev Chonoles Feb 22 '13 at 13:24

@Amzoti: It's hard to explain, I'm not mathematician, but I trying... I generated a table for this triple (1,37,41) with possible remainder for small primes:

n mod p:

3:[ 1] 0

5:[ 2] 0 1

7:[ 2] 0 2

11:[ 3] 0 5 7

13:[ 2] 0 10

17:[ 4] 0 1 10 13

19:[ 5] 0 7 12 16 17

23:[ 6] 0 13 15 17 19 21

29:[ 7] 0 4 11 13 15 17 25

31:[ 7] 0 2 4 8 14 17 25

37:[ 1] 8

41:[ 1] 30

43:[10] 0 6 7 15 18 20 23 29 35 39

... and so on. And n+1, 37n+1, 41n+1 must be prime.

Details: ZHENXIANG ZHANG:FINDING C3-STRONG PSEUDOPRIMES

Another example number: 2809386136371438866496346539320857607283794588353401165473007394921174159995576890097633348301878401799853448496604965862616291048652062065394646956750323263193037964463262192320342740843556773326129475220032687577421757298519461662249735906372935033549531355723541168448473213797808686850657266188854910604399375221284468243956369013816289853351613404802033369894673267294395882499368769744558478456847832293372532910707925159549055961870528474205973317584333504757691137280936247019772992086410290579840045352494329434008415453636962234340836064927449224611783307531275541463776950841504387756099277118377038405235871794332425052938384904092351280663156507379159650872073401637805282499411435158581593146712826943388219341340599170371727498381901415081480224172469034841153893464174362543356514320522139692755430021327765409775374978255770027259819794532960997484676733140078317807018465818200888425898964847614568913543667470861729894161917981606153150551439410460813448153180857197888310572079656577579695814664713878369660173739371415918888444922272634772987239224582905405240454751027613993535619787590841842251056960329294514093407010964283471430374834873427180817297408975879673867

(1189 digits)

This number is a strong pseudoprime for all (168) prime bases below 1000. It is a Carmichael number too, with the same format.

Reg.: Joe53

share|improve this answer

197475 704297076 769879318 479365782 605729426 528421984 294554780 711762857 505669370 986517424 096751829 488980502 254269692 200841641 288349940 843678305 321105903 510536750 100514089 183274534 482451736 946316424 510377404 498460285 069545777 656519289 729095553 895011368 091845754 887799208 568313368 087677010 037387886 257331969 473598709 629563758 316982529 541918503 729974147 573401550 326647431 929654622 465970387 164330994 694720288 156577774 827473110 333350092 369949083 055692184 067330157 343079442 986832268 281420578 909681133 401657075 403304506 177944890 621300718 745594728 786819988 830295725 434492922 853465829 752746870 734788604 359697581 532651202 427729467

(618 digits)

This number is a strong pseudoprime for all (100) prime bases up to 541. It is a Carmichael number with 3 prime factors, with format: N = (n+1)(37n+1)(41n+1)

Reg.: Joe53

share|improve this answer
1  
How did you construct it? Regards –  Amzoti Aug 11 '13 at 13:18

D=4*3*5*7*11*13*17*19*23*29*31*37*41*43*47*53*59*61*67*71*73*79*83*89*97

P=3864905207490318811+ i * D - where i=0,1,2,3...

Q=37*P-36

R=41*P-40

if P, Q, R are all primes (SPRP-2 in practice), than N=P*Q*R is may be a strong pseudoprime for all (25) prime bases below 100 - but its not random bases, which uses MR-test.

Examples: i= 0, 2896, 3246, 5745, 6128, 8134, 9402, 10075, ...

or P=41837477983818300631+ i * D , Q=13*P-12 , R=17*P-16 , i=0, 645, 1469, 2744, 3186, 3713,...

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.