Some Continued Fraction Algorithms

[ttw]

Another number theory program using HP50g's big integer capability.

Given a prime, M, and a non-zero number, A, "pRoot" determines if A is a quadratic residue for M,
and if not, if A is a primitive root of M. A being a primitive root means A can be used a multiplier
for a Linear Congruential Generator, with M as modulus (with no additive term.) While these generators are
not cryptgraphcally secure, the lower order bits have much less structure than the low order bits of M being a power of two.

« MIN LASTARG MAX DUP 1 - 0 0 -> A M M1 D N «
1 SF M MODSTO M1 DIVIS REVLIST DUP 'D' STO
SIZE 'N' STO A D 2 GET POWMOD
IF 1 == THEN 1 CF M A "Residue" END
IF 1 FS? THEN 3 N 1 - FOR I
A D I GET POWMOD IF 1 == THEN N 3 + 'I' STO 1 CF END NEXT
M A IF 1 FS? THEN
"Primitive Root"
ELSE
"Non Root"
END »»

If A is a quadratic residue and M = 1 Mod 4, then these can be used to construct
a quadratic random number generator that has nice properties (though I haven't really
tried to prove anything.)