Carmichael 3 strong pseudoprimes: Difference between revisions

Line 1:

A lot of composite numbers can be seperated from primes by ~~Fermats~~ 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.

A lot of composite numbers can be seperated 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].

Line 9:

:<tt>g=h3+Prime1</tt>

:<tt>for 0 < d < h3+Prime1</tt>

::<tt>if (h3+Prime1)*(Prime1-1) mod d == 0 and -Prime1 squared mod h3 == d mod h3</tt>

::<tt>then</tt>

:::<tt>Prime2 = 1 + ((Prime1-1) * g/d)</tt>

:::<tt>Prime2 = 1 + ((Prime1-1) * (h3+Prime1)/d)</tt>

:::<tt>next d if Prime2 is not prime</tt>

:::<tt>Prime3 = 1 + (Prime1*Prime2/h3)</tt>

@@ Line 1: / Line 1: @@
 {{task}}
-A lot of composite numbers can be seperated from primes by Fermats 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.
+A lot of composite numbers can be seperated 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].
@@ Line 9: / Line 9: @@
 <tt>for 1 < h3 < Prime<sub>1</sub></tt>
-:<tt>g=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) * g/d)</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>