Carmichael 3 strong pseudoprimes: Difference between revisions

Content added Content deleted
No edit summary
m (added whitespace before the TOC (table of contents), added a ;Task: (bold) header, added other whitespace to the task's preamble.)
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   [[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:
⚫
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].
Find Carmichael numbers of the form:
:::: <math> Prime_1 \times Prime_2 \times Prime_3 </math>


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).
where &nbsp; (<math> Prime_1 < Prime_2 < Prime_3</math>) &nbsp; for all &nbsp; <math> Prime_1 </math> &nbsp; up to &nbsp; '''61'''.
<br>(See page 7 of &nbsp; [http://www.maths.lancs.ac.uk/~jameson/carfind.pdf Notes by G.J.O Jameson March 2010] &nbsp; for solutions.)




'''Pseudocode:'''<br>For a given <math>Prime_1</math>
;Pseudocode:
For a given &nbsp; <math> Prime_1 </math>


<tt>for 1 < h3 < Prime<sub>1</sub></tt>
<tt>for 1 < h3 < Prime<sub>1</sub></tt>
:<tt>for 0 < d < 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>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>then</tt>
:::<tt>Prime<sub>2</sub> = 1 + ((Prime<sub>1</sub>-1) * (h3+Prime<sub>1</sub>)/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>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>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>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>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>
<br><br>


Retrieved from "https://rosettacode.org/wiki/Carmichael_3_strong_pseudoprimes"