blob: e426705ec1eba930c06235a0f88e0dfb0c8957c1 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
|
##
## This is the file `numtheory.tcl',
## generated with the SAK utility
## (sak docstrip/regen).
##
## The original source files were:
##
## numtheory.dtx (with options: `pkg')
##
## In other words:
## **************************************
## * This Source is not the True Source *
## **************************************
## the true source is the file from which this one was generated.
##
# Copyright (c) 2010 by Lars Hellstrom. All rights reserved.
# See the file "license.terms" for information on usage and redistribution
# of this file, and for a DISCLAIMER OF ALL WARRANTIES.
package require Tcl 8.5
package provide math::numtheory 1.0
namespace eval ::math::numtheory {
namespace export isprime
}
proc ::math::numtheory::prime_trialdivision {n} {
if {$n<2} then {return -code return 0}
if {$n<4} then {return -code return 1}
if {$n%2 == 0} then {return -code return 0}
if {$n<9} then {return -code return 1}
if {$n%3 == 0} then {return -code return 0}
if {$n%5 == 0} then {return -code return 0}
if {$n%7 == 0} then {return -code return 0}
if {$n<121} then {return -code return 1}
}
proc ::math::numtheory::Miller--Rabin {n s d a} {
set x 1
while {$d>1} {
if {$d & 1} then {set x [expr {$x*$a % $n}]}
set a [expr {$a*$a % $n}]
set d [expr {$d >> 1}]
}
set x [expr {$x*$a % $n}]
if {$x == 1} then {return 0}
for {} {$s>1} {incr s -1} {
if {$x == $n-1} then {return 0}
set x [expr {$x*$x % $n}]
if {$x == 1} then {return 1}
}
return [expr {$x != $n-1}]
}
proc ::math::numtheory::isprime {n args} {
prime_trialdivision $n
set d [expr {$n-1}]; set s 0
while {($d&1) == 0} {
incr s
set d [expr {$d>>1}]
}
if {[Miller--Rabin $n $s $d 2]} then {return 0}
if {$n < 2047} then {return 1}
if {[Miller--Rabin $n $s $d 3]} then {return 0}
if {$n < 1373653} then {return 1}
if {[Miller--Rabin $n $s $d 5]} then {return 0}
if {$n < 25326001} then {return 1}
if {[Miller--Rabin $n $s $d 7] || $n==3215031751} then {return 0}
if {$n < 118670087467} then {return 1}
array set O {-randommr 4}
array set O $args
for {set i $O(-randommr)} {$i >= 1} {incr i -1} {
if {[Miller--Rabin $n $s $d [expr {(
(round(rand()*0x100000000)-1)
*3 | 1)
+ 10
}]]} then {return 0}
}
return on
}
##
##
## End of file `numtheory.tcl'.
|
