33 lines
1.9 KiB
Plaintext
33 lines
1.9 KiB
Plaintext
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].
|
|
|
|
|
|
;Task:
|
|
Find Carmichael numbers of the form:
|
|
:::: <big> <i>Prime</i><sub>1</sub> × <i>Prime</i><sub>2</sub> × <i>Prime</i><sub>3</sub> </big>
|
|
|
|
where <big> (<i>Prime</i><sub>1</sub> < <i>Prime</i><sub>2</sub> < <i>Prime</i><sub>3</sub>) </big> for all <big> <i>Prime</i><sub>1</sub> </big> up to '''61'''.
|
|
<br>(See page 7 of [http://www.maths.lancs.ac.uk/~jameson/carfind.pdf Notes by G.J.O Jameson March 2010] for solutions.)
|
|
|
|
|
|
;Pseudocode:
|
|
For a given '''Prime<sub>1</sub>'''
|
|
|
|
<tt>for 1 < h3 < Prime<sub>1</sub></tt>
|
|
<tt>for 0 < d < h3+Prime<sub>1</sub></tt>
|
|
<tt>if (h3+Prime<sub>1</sub>)*(Prime<sub>1</sub>-1) mod d == 0 and -Prime<sub>1</sub> squared mod h3 == d mod h3</tt>
|
|
<tt>then</tt>
|
|
<tt>Prime<sub>2</sub> = 1 + ((Prime<sub>1</sub>-1) * (h3+Prime<sub>1</sub>)/d)</tt>
|
|
<tt>next d if Prime<sub>2</sub> is not prime</tt>
|
|
<tt>Prime<sub>3</sub> = 1 + (Prime<sub>1</sub>*Prime<sub>2</sub>/h3)</tt>
|
|
<tt>next d if Prime<sub>3</sub> is not prime</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>
|
|
<br><br>
|
|
;related task
|
|
[[Chernick's Carmichael numbers]]
|
|
<br><br>
|