0C9006 |
^ZFactor
|
( Zs → Lf )
Factors signed long integer.
|
0CA006 |
^NFactor
|
( z → {} )
Factors positive long integer.
|
0CB006 |
^NFactorSpc
|
( z → {} )
Semi-factors positive long integer. This is
regular factorization with an extra
'hopeless?' test.
|
0CD006 |
^SFactor
|
( S → Lf )
Factors short integer. Pollard Rho, with the
assumption that trial division has been done
already. Thus any factor less than 4012009 is
known to be a prime, for greater factors a
primality test is used before calling the
actual Pollard Rho. Pollard Rho does not
find the factors in order of magnitude, thus
the results will be sorted after full
factorization has been achieved.
|
0CE006 |
^SPollard
|
( S → S1 S2 )
Factors short integer into 2 parts using
Pollard Rho algorithm. Trial division and
primality tests should be done prior to
calling this subroutine, otherwise an eternal
loop is risked. The random number generator
is modeled after the user level RAND command,
although the starting value is different.
|
0CF006 |
^BFactor
|
( N → Lf )
Factors long integer. Brent-Pollard, with the
assumption that trial division has been done
already. When a small factor is found SFactor
is called to get full short
factorization. Since the factorization can
potentially take a very long time, an
execution time test is used to abort
factoring very long integers (limit is 60s
for each composite). The factors are sorted
at exit.
|
0D0006 |
^BrentPow
|
( Za Z1 Z2 Zn #k → Z )
Modular * + ^ mod for Brent-Pollard
factorization. Output is Z1*Z2+Za mod Zn
repeated k times Note that k=0 and k=1 give
the same result. Also Z1≠Z2 makes no sense
for k≠0. All arguments are assumed to be
positive. Za is assumed to be < 16. In some
instances k can be a very high number, thus
it might make sense to use Montgomery
multiplication.
|
0D1006 |
^ZPrime?
|
( Z → flag )
Primality test for a positive integer.
According to Pinch commercial software
packages use only about 5-10 bases by
default, maximum around 25. The latest
versions usually implement a deterministic.
|
0D2006 |
^ZIsPrime?
|
( Z → flag )
Probabilistic primality test for a positive
integer.
|
0D3006 |
^SIsPrime?
|
( S → flag )
Tests if positive short Z is prime. M-R test
fails for integers ≤ 3, so we just test them
separately at the start. For convenience lets
define 0 and 1 to be primes also.
|
0D4006 |
^BIsPrime?
|
( S → flag )
Test if positive long Z is prime.
|
0D5006 |
^BRabin
|
( Z #base → Z flag )
Performs Miller-Rabin test for long positive
integer. Returns TRUE if base witnesses
composite. Else returns FALSE.
|
0D6006 |
^ZTrialDiv2
|
( Z → Z' #n )
Remove factors of 2 from integer.
#n is the power of two extracted from the
number. The sign is also handled correctly,
even though it is never required in ALG48
(absolute Z).
|
0D7006 |
^ZTrialPrime?
|
( Z → flag )
Trial division primality test for a positive
integer. works for Z ≥ 3 (return false for
Z=2).
|
0D8006 |
^ZTrialDiv
|
( Z → Mf Z' )
Trial division of a positive integer. If Z'
is one then full factorization was achieved.
The long trial division is not too slow,
since division by short integer is quite
fast. The quotient is also checked so that a
final factor less than 2000^2 will also be
automatically detected.
|
0C7006 |
^Prime+
|
( Z → Z' )
Returns next prime ( Z' > Z ).
|
0C8006 |
^Prime-
|
( Z → Z' )
Returns previous prime ( Z' < Z ).
|