Carmichael 3 strong pseudoprimes: Difference between revisions
Content added Content deleted
(→{{header|Java}}: added Java) |
m (added whitespace before the TOC.) |
||
| Line 1: | Line 1: | ||
{{task}} |
{{task}} |
||
A lot of composite numbers can be separated from primes by Fermat's Little Theorem, but there are some that completely confound it |
A lot of composite numbers can be separated from primes by Fermat's Little Theorem, but there are some that completely confound it. |
||
The [[Miller-Rabin primality test|Miller Rabin Test]] uses a combination of Fermat's Little Theorem and Chinese Division Theorem to overcome this. |
|||
The purpose of this task is to investigate such numbers using a method based on [[wp:Carmichael number|Carmichael numbers]], as suggested in [http://www.maths.lancs.ac.uk/~jameson/carfind.pdf Notes by G.J.O Jameson March 2010]. |
The purpose of this task is to investigate such numbers using a method based on [[wp:Carmichael number|Carmichael numbers]], as suggested in [http://www.maths.lancs.ac.uk/~jameson/carfind.pdf Notes by G.J.O Jameson March 2010]. |
||
The objective is to find Carmichael numbers of the form <math>Prime_1 \times Prime_2 \times Prime_3</math> (where <math>Prime_1 < Prime_2 < Prime_3</math>) for all <math>Prime_1</math> up to 61 (see page 7 of [http://www.maths.lancs.ac.uk/~jameson/carfind.pdf Notes by G.J.O Jameson March 2010] for solutions). |
The objective is to find Carmichael numbers of the form <math>Prime_1 \times Prime_2 \times Prime_3</math> (where <math>Prime_1 < Prime_2 < Prime_3</math>) for all <math>Prime_1</math> up to 61 (see page 7 of [http://www.maths.lancs.ac.uk/~jameson/carfind.pdf Notes by G.J.O Jameson March 2010] for solutions). |
||
'''Pseudocode:'''<br>For a given <math>Prime_1</math> |
'''Pseudocode:'''<br>For a given <math>Prime_1</math> |
||
| Line 18: | Line 21: | ||
:::<tt>next d if (Prime<sub>2</sub>*Prime<sub>3</sub>) mod (Prime<sub>1</sub>-1) not equal 1</tt> |
:::<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> |
:::<tt>Prime<sub>1</sub> * Prime<sub>2</sub> * Prime<sub>3</sub> is a Carmichael Number</tt> |
||
<br><br> |
|||
=={{header|Ada}}== |
=={{header|Ada}}== |
||