Carmichael 3 strong pseudoprimes: Difference between revisions
Content added Content deleted
No edit summary |
|||
Line 21:
=={{header|Ruby}}==
<lang ruby>
# Generate Charmichael Numbers
#
# Nigel_Galloway
# November 30th., 2012.
#
require 'prime'
Integer.each_prime(61) {|p|
(2...p).each {|h3|
g = h3+p
(1...g).each {|d|
if (g*(p-1)) % d == 0 and (-1*p*p) % h3 == d % h3 then
q = 1+((p-1)*g/d)
next if not q.prime?
r = 1+(p*q/h3)
next if not r.prime? or not (q*r) % (p-1) == 1
puts "#{p} X #{q} X #{r}"
end
}
}
puts ""
}
</lang>
{{out}}
<pre>
3 X 11 X 17
5 X 29 X 73
5 X 17 X 29
5 X 13 X 17
7 X 19 X 67
7 X 31 X 73
7 X 13 X 31
7 X 23 X 41
7 X 73 X 103
7 X 13 X 19
13 X 61 X 397
13 X 37 X 241
13 X 97 X 421
13 X 37 X 97
13 X 37 X 61
17 X 41 X 233
17 X 353 X 1201
19 X 43 X 409
19 X 199 X 271
23 X 199 X 353
29 X 113 X 1093
29 X 197 X 953
31 X 991 X 15361
31 X 61 X 631
31 X 151 X 1171
31 X 61 X 271
31 X 61 X 211
31 X 271 X 601
31 X 181 X 331
37 X 109 X 2017
37 X 73 X 541
37 X 613 X 1621
37 X 73 X 181
37 X 73 X 109
41 X 1721 X 35281
41 X 881 X 12041
41 X 101 X 461
41 X 241 X 761
41 X 241 X 521
41 X 73 X 137
41 X 61 X 101
43 X 631 X 13567
43 X 271 X 5827
43 X 127 X 2731
43 X 127 X 1093
43 X 211 X 757
43 X 631 X 1597
43 X 127 X 211
43 X 211 X 337
43 X 433 X 643
43 X 547 X 673
43 X 3361 X 3907
47 X 3359 X 6073
47 X 1151 X 1933
47 X 3727 X 5153
53 X 157 X 2081
53 X 79 X 599
53 X 157 X 521
59 X 1451 X 2089
61 X 421 X 12841
61 X 181 X 5521
61 X 1301 X 19841
61 X 277 X 2113
61 X 181 X 1381
61 X 541 X 3001
61 X 661 X 2521
61 X 271 X 571
61 X 241 X 421
61 X 3361 X 4021
</pre>
|
Revision as of 12:31, 30 November 2012
Template:Draft Task A lot of composite numbers can be detected by the Miller Rabin Test, but there are some that evade it.
The purpose of this task is to investigate such numbers. The method suggested is based on ....
The objective is to find Carmichael numbers of the form Prime1 X Prime2 X Prime3. Prime1 < Prime2 < Prime3 for all Prime1 upto 61 see page 7 of.
For a given Prime1
for 1 < h3 < Prime1
for 0 < d < h3+Prime1 if (h3+Prime1)*(Prime1-1) mod d == 0 and -Prime1 squared mod h3 == d mod h3 then Prime2 = 1 + ((Prime1-1) * g/d) next d if Prime2 is not prime Prime3 = 1 + (Prime1*Prime2/h3) next d if Prime3 is not prime next d if (Prime2*Prime3) mod (Prime1-1) not equal 1 Prime1 * Prime2 * Prime3 is a Carmichael Number
Ruby
<lang ruby>
- Generate Charmichael Numbers
- Nigel_Galloway
- November 30th., 2012.
require 'prime' Integer.each_prime(61) {|p|
(2...p).each {|h3| g = h3+p (1...g).each {|d| if (g*(p-1)) % d == 0 and (-1*p*p) % h3 == d % h3 then q = 1+((p-1)*g/d) next if not q.prime? r = 1+(p*q/h3) next if not r.prime? or not (q*r) % (p-1) == 1 puts "#{p} X #{q} X #{r}" end } } puts ""
} </lang>
- Output:
3 X 11 X 17 5 X 29 X 73 5 X 17 X 29 5 X 13 X 17 7 X 19 X 67 7 X 31 X 73 7 X 13 X 31 7 X 23 X 41 7 X 73 X 103 7 X 13 X 19 13 X 61 X 397 13 X 37 X 241 13 X 97 X 421 13 X 37 X 97 13 X 37 X 61 17 X 41 X 233 17 X 353 X 1201 19 X 43 X 409 19 X 199 X 271 23 X 199 X 353 29 X 113 X 1093 29 X 197 X 953 31 X 991 X 15361 31 X 61 X 631 31 X 151 X 1171 31 X 61 X 271 31 X 61 X 211 31 X 271 X 601 31 X 181 X 331 37 X 109 X 2017 37 X 73 X 541 37 X 613 X 1621 37 X 73 X 181 37 X 73 X 109 41 X 1721 X 35281 41 X 881 X 12041 41 X 101 X 461 41 X 241 X 761 41 X 241 X 521 41 X 73 X 137 41 X 61 X 101 43 X 631 X 13567 43 X 271 X 5827 43 X 127 X 2731 43 X 127 X 1093 43 X 211 X 757 43 X 631 X 1597 43 X 127 X 211 43 X 211 X 337 43 X 433 X 643 43 X 547 X 673 43 X 3361 X 3907 47 X 3359 X 6073 47 X 1151 X 1933 47 X 3727 X 5153 53 X 157 X 2081 53 X 79 X 599 53 X 157 X 521 59 X 1451 X 2089 61 X 421 X 12841 61 X 181 X 5521 61 X 1301 X 19841 61 X 277 X 2113 61 X 181 X 1381 61 X 541 X 3001 61 X 661 X 2521 61 X 271 X 571 61 X 241 X 421 61 X 3361 X 4021