<![CDATA[size : 11739
uploaded_on : Mon May 17 00:00:00 1999
modified_on : Wed Dec 8 14:03:40 1999
title : BigPrime
org_filename : Bigprime.pas
author : Jes R. Klinke
authoremail : jesk@diku.dk
description : Routines for finding and manipulating arbitrarily large (at least 200 digits) primes. Requires BigNum.
keywords :
tested : not tested yet
submitted_by : The CKB Crew
submitted_by_email : ckb@netalive.org
uploaded_by : nobody
modified_by : nobody
owner : nobody
lang : pas
file-type : text/plain
category : pascal-alg-maths
__END_OF_HEADER__
unit BigPrime;
{ BigPrime v2.1, 32-bit for Delphi by Jes R. Klinke
This unit provides means for finding very large prime numbers and other
functions nessecary for serious cryptographic applications.
The sequential prime search algorithm is due to Philip Zimmermann
Features:
* Test and search for probable primes
Function are provided for finding really large primes. 100 digits in a
matter of seconds, 200 digits in about a minute (120 MHz Pentium).
* Calculation of inverse
A function which given E and M finds D such that (E * D) mod M = 1
is useful for RSA key generation.
Any comment or bug reports are welcome.
You can reach me at jesk@diku.dk or jesk@dk-online.dk.
My snail-mail address is Jes Rahbek Klinke
Haandvaerkerhaven 3, 2. mf
2400 Copenhagen NV }
interface
uses
BigNum;
function FermatTest(Candidate: TBigNum; MaxFermatBase: Integer): Boolean;
{ Test if a given number is a probable prime.
On a false return the number is definately not a prime.
On a true return the number is probably a prime, the higher the value
of MaxFermatBase, the less likely that the numer is really composite.
The minimum value, 2, will usually suffise. }
procedure ZimmermannSearch(Start: TBigNum; MaxFermatBase: Integer);
{ Seaches for the smallest probable prime greater than or equal to Start.
The result is also returned in the parameter Start. }
function RelativePrime(N, M: TBigNum): Boolean;
{ Tests if N is relatively prime to M, i.e. the smallest integer dividing
them both is 1. }
procedure Inverse(E, M: TBigNum);
{ Given E and M finds D such that (E * D) mod M = 1 }
implementation
const
PrimeTableSize = 1028;
PrimeTable: array [0..PrimeTableSize - 1] of Integer = (
2, 3, 5, 7, 11, 13, 17, 19,
23, 29, 31, 37, 41, 43, 47, 53,
59, 61, 67, 71, 73, 79, 83, 89,
97, 101, 103, 107, 109, 113, 127, 131,
137, 139, 149, 151, 157, 163, 167, 173,
179, 181, 191, 193, 197, 199, 211, 223,
227, 229, 233, 239, 241, 251, 257, 263,
269, 271, 277, 281, 283, 293, 307, 311,
313, 317, 331, 337, 347, 349, 353, 359,
367, 373, 379, 383, 389, 397, 401, 409,
419, 421, 431, 433, 439, 443, 449, 457,
461, 463, 467, 479, 487, 491, 499, 503,
509, 521, 523, 541, 547, 557, 563, 569,
571, 577, 587, 593, 599, 601, 607, 613,
617, 619, 631, 641, 643, 647, 653, 659,
661, 673, 677, 683, 691, 701, 709, 719,
727, 733, 739, 743, 751, 757, 761, 769,
773, 787, 797, 809, 811, 821, 823, 827,
829, 839, 853, 857, 859, 863, 877, 881,
883, 887, 907, 911, 919, 929, 937, 941,
947, 953, 967, 971, 977, 983, 991, 997,
1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049,
1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097,
1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163,
1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223,
1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283,
1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321,
1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423,
1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459,
1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511,
1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571,
1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619,
1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693,
1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747,
1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811,
1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877,
1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949,
1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003,
2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069,
2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129,
2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203,
2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267,
2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311,
2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377,
2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423,
2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503,
2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579,
2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657,
2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693,
2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741,
2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801,
2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861,
2879, 2887, 2897, 2903, 2909, 2917, 2927, 2939,
2953, 2957, 2963, 2969, 2971, 2999, 3001, 3011,
3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079,
3083, 3089, 3109, 3119, 3121, 3137, 3163, 3167,
3169, 3181, 3187, 3191, 3203, 3209, 3217, 3221,
3229, 3251, 3253, 3257, 3259, 3271, 3299, 3301,
3307, 3313, 3319, 3323, 3329, 3331, 3343, 3347,
3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413,
3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491,
3499, 3511, 3517, 3527, 3529, 3533, 3539, 3541,
3547, 3557, 3559, 3571, 3581, 3583, 3593, 3607,
3613, 3617, 3623, 3631, 3637, 3643, 3659, 3671,
3673, 3677, 3691, 3697, 3701, 3709, 3719, 3727,
3733, 3739, 3761, 3767, 3769, 3779, 3793, 3797,
3803, 3821, 3823, 3833, 3847, 3851, 3853, 3863,
3877, 3881, 3889, 3907, 3911, 3917, 3919, 3923,
3929, 3931, 3943, 3947, 3967, 3989, 4001, 4003,
4007, 4013, 4019, 4021, 4027, 4049, 4051, 4057,
4073, 4079, 4091, 4093, 4099, 4111, 4127, 4129,
4133, 4139, 4153, 4157, 4159, 4177, 4201, 4211,
4217, 4219, 4229, 4231, 4241, 4243, 4253, 4259,
4261, 4271, 4273, 4283, 4289, 4297, 4327, 4337,
4339, 4349, 4357, 4363, 4373, 4391, 4397, 4409,
4421, 4423, 4441, 4447, 4451, 4457, 4463, 4481,
4483, 4493, 4507, 4513, 4517, 4519, 4523, 4547,
4549, 4561, 4567, 4583, 4591, 4597, 4603, 4621,
4637, 4639, 4643, 4649, 4651, 4657, 4663, 4673,
4679, 4691, 4703, 4721, 4723, 4729, 4733, 4751,
4759, 4783, 4787, 4789, 4793, 4799, 4801, 4813,
4817, 4831, 4861, 4871, 4877, 4889, 4903, 4909,
4919, 4931, 4933, 4937, 4943, 4951, 4957, 4967,
4969, 4973, 4987, 4993, 4999, 5003, 5009, 5011,
5021, 5023, 5039, 5051, 5059, 5077, 5081, 5087,
5099, 5101, 5107, 5113, 5119, 5147, 5153, 5167,
5171, 5179, 5189, 5197, 5209, 5227, 5231, 5233,
5237, 5261, 5273, 5279, 5281, 5297, 5303, 5309,
5323, 5333, 5347, 5351, 5381, 5387, 5393, 5399,
5407, 5413, 5417, 5419, 5431, 5437, 5441, 5443,
5449, 5471, 5477, 5479, 5483, 5501, 5503, 5507,
5519, 5521, 5527, 5531, 5557, 5563, 5569, 5573,
5581, 5591, 5623, 5639, 5641, 5647, 5651, 5653,
5657, 5659, 5669, 5683, 5689, 5693, 5701, 5711,
5717, 5737, 5741, 5743, 5749, 5779, 5783, 5791,
5801, 5807, 5813, 5821, 5827, 5839, 5843, 5849,
5851, 5857, 5861, 5867, 5869, 5879, 5881, 5897,
5903, 5923, 5927, 5939, 5953, 5981, 5987, 6007,
6011, 6029, 6037, 6043, 6047, 6053, 6067, 6073,
6079, 6089, 6091, 6101, 6113, 6121, 6131, 6133,
6143, 6151, 6163, 6173, 6197, 6199, 6203, 6211,
6217, 6221, 6229, 6247, 6257, 6263, 6269, 6271,
6277, 6287, 6299, 6301, 6311, 6317, 6323, 6329,
6337, 6343, 6353, 6359, 6361, 6367, 6373, 6379,
6389, 6397, 6421, 6427, 6449, 6451, 6469, 6473,
6481, 6491, 6521, 6529, 6547, 6551, 6553, 6563,
6569, 6571, 6577, 6581, 6599, 6607, 6619, 6637,
6653, 6659, 6661, 6673, 6679, 6689, 6691, 6701,
6703, 6709, 6719, 6733, 6737, 6761, 6763, 6779,
6781, 6791, 6793, 6803, 6823, 6827, 6829, 6833,
6841, 6857, 6863, 6869, 6871, 6883, 6899, 6907,
6911, 6917, 6947, 6949, 6959, 6961, 6967, 6971,
6977, 6983, 6991, 6997, 7001, 7013, 7019, 7027,
7039, 7043, 7057, 7069, 7079, 7103, 7109, 7121,
7127, 7129, 7151, 7159, 7177, 7187, 7193, 7207,
7211, 7213, 7219, 7229, 7237, 7243, 7247, 7253,
7283, 7297, 7307, 7309, 7321, 7331, 7333, 7349,
7351, 7369, 7393, 7411, 7417, 7433, 7451, 7457,
7459, 7477, 7481, 7487, 7489, 7499, 7507, 7517,
7523, 7529, 7537, 7541, 7547, 7549, 7559, 7561,
7573, 7577, 7583, 7589, 7591, 7603, 7607, 7621,
7639, 7643, 7649, 7669, 7673, 7681, 7687, 7691,
7699, 7703, 7717, 7723, 7727, 7741, 7753, 7757,
7759, 7789, 7793, 7817, 7823, 7829, 7841, 7853,
7867, 7873, 7877, 7879, 7883, 7901, 7907, 7919,
7927, 7933, 7937, 7949, 7951, 7963, 7993, 8009,
8011, 8017, 8039, 8053, 8059, 8069, 8081, 8087,
8089, 8093, 8101, 8111, 8117, 8123, 8147, 8161,
8167, 8171, 8179, 8191);
function FermatTest(Candidate: TBigNum; MaxFermatBase: Integer): Boolean;
var
Base, BaseCopy, Exp: TBigNum;
begin
if Candidate.Negative then
raise EBigNumInvalidArg.Create('Negative prime candidate in FermatTest');
Base := TBigNum.Create;
BaseCopy := TBigNum.Create;
Exp := TBigNum.Create;
Result := True;
Base.AsLong := 2;
while Result and (Base.AsLong <= MaxFermatBase) do
begin
BaseCopy.Assign(Base);
Exp.Assign(Candidate);
Exp.AbsDecrement(1);
BaseCopy.PowerModulo(Exp, Candidate);
Exp.AsLong := 1;
Result := BaseCopy.Compare(Exp) = 0;
Base.AbsIncrement(1);
end;
Exp.Destroy;
BaseCopy.Destroy;
Base.Destroy;
end;
procedure ZimmermannSearch(Start: TBigNum; MaxFermatBase: Integer);
type
PRemainderTable = ^TRemainderTable;
TRemainderTable = array [0..PrimeTableSize - 1] of Integer;
var
RemainderTable: PRemainderTable;
Delta: Integer;
procedure InitRemainderTable(Start: TBigNum; RemainderTable: PRemainderTable);
var
I: Integer;
begin
for I := 0 to PrimeTableSize - 1 do
RemainderTable^[I] := Start.AbsModuloLong(PrimeTable[I]);
end;
function RemainderTest(Delta: Integer; RemainderTable: PRemainderTable): Boolean;
var
I: Integer;
begin
Result := True;
I := 0;
while Result and (I < PrimeTableSize) do
begin
Result := not ((RemainderTable^[I] + Delta) mod PrimeTable[I] = 0);
Inc(I);
end;
end;
begin
if Start.Negative then
Start.AsLong := PrimeTable[PrimeTableSize - 1];
if Start.AbsModuloLong(2) = 0 then
Start.AbsIncrement(1);
New(RemainderTable);
InitRemainderTable(Start, RemainderTable);
Delta := 0;
while not (RemainderTest(Delta, RemainderTable) and FermatTest(Start, MaxFermatBase)) do
begin
Inc(Delta, 2);
Start.AbsIncrement(2);
end;
Dispose(RemainderTable);
end;
function RelativePrime(N, M: TBigNum): Boolean;
var
TempN, TempM, I: TBigNum;
begin
if N.Negative or M.Negative then
raise EBigNumInvalidArg.Create('Negative argument in RelativePrime');
TempN := TBigNum.Create;
TempM := TBigNum.Create;
I := TBigNum.Create;
TempN.Assign(N);
TempM.Assign(M);
I.AsLong := 0;
while I.Compare(TempM) <> 0 do
begin
if TempM.Compare(TempN) = 1 then
TempM.Swap(TempN)
else
TempN.Modulo(TempM);
end;
I.AsLong := 1;
Result := I.Compare(TempN) = 0;
end;
procedure Inverse(E, M: TBigNum);
var
TempM: TBigNum;
procedure Euklid(A, B: TBigNum);
var
NA, NB, Test, Q: TBigNum;
begin
Test := TBigNum.Create;
try
Test.AsLong := 1;
if A.Compare(Test) <= 0 then
begin
if A.Compare(Test) < 0 then
raise EBigNumInvalidArg.Create('No inverse exists in Inverse');
end
else
begin
Test.AsLong := 0;
if B.Compare(Test) <= 0 then
raise EBigNumInvalidArg.Create('No inverse exists in Inverse');
NA := TBigNum.Create;
NB := TBigNum.Create;
Q := TBigNum.Create;
NA.Assign(B);
NB.Assign(A);
NB.Modulo(B);
Q.Assign(A);
Q.Divide(B);
Euklid(NA, NB);
A.Assign(NB);
B.Assign(NA);
NB.Multiply(Q);
B.Subtract(NB);
Q.Destroy;
NA.Destroy;
NB.Destroy;
end;
finally
Test.Destroy;
end;
end;
begin
TempM := TBigNum.Create;
TempM.Assign(M);
Euklid(TempM, E);
E.Modulo(M);
TempM.Destroy;
end;
end.
]]>