Anonymous user
Carmichael 3 strong pseudoprimes: Difference between revisions
Carmichael 3 strong pseudoprimes (view source)
Revision as of 15:40, 31 December 2012
, 11 years agotidy up task description
(Shorer D entry) |
m (tidy up task description) |
||
Line 1:
{{task}}
A lot of composite numbers can be detected by the [[Miller-Rabin primality test|Miller Rabin Test]], but there are some that evade it.
The
'''Pseudocode:'''<br>For a given <math>Prime_1</math>
▲:Prime1 < Prime2 < Prime3 for all Prime1 upto 61 see page 7 of [http://www.maths.lancs.ac.uk/~jameson/carfind.pdf Notes by G.J.O Jameson March 2010].
<tt>for 1 < h3 < Prime<sub>1</sub></tt>
:<tt>g=h3+Prime<sub>1</sub></tt>
:<tt>for
::<tt>if (h3+
::<tt>then</tt>
:::<tt>Prime<sub>2</sub> = 1 + ((Prime<sub>1</sub>-1) * g/d)</tt>
▲::if (h3+Prime1)*(Prime1-1) mod d == 0 and -Prime1 squared mod h3 == d mod h3
:::<tt>Prime<sub>3</sub> = 1 + (Prime<sub>1</sub>*Prime<sub>2</sub>/h3)</tt>
:::<tt>next d if
:::<tt>next d if (Prime<sub>2</sub>*Prime<sub>3</sub>) mod (Prime<sub>1</sub>-1) not equal 1</tt>
:::<tt>Prime<sub>1</sub> * Prime<sub>2</sub> * Prime<sub>3</sub> is a Carmichael Number</tt>
▲:::next d if Prime3 is not prime
=={{header|D}}==
Line 140 ⟶ 133:
=={{header|Haskell}}==
{{trans|Ruby}}
{{libheader|primes}}
{{Works with|GHC|7.4.1}}
{{Works with|primes|0.2.1.0}}
<lang haskell>#!/usr/bin/runhaskell
Line 173 ⟶ 164:
main = putStr $ unlines $ map show carmichaels</lang>
{{out}}
<pre>
(3,11,17)
Line 600 ⟶ 589:
=={{header|Ruby}}==
<lang ruby># Generate Charmichael Numbers
#
# Nigel_Galloway
Line 621 ⟶ 609:
}
puts ""
}</lang>▼
▲</lang>
{{out}}
<pre style="height:30ex;overflow:scroll">
| |||