www.pudn.com > RSA_delphi.rar > FGInt.pas, change:2002-11-13,size:65743b


{License, info, etc 
 ------------------ 
 
This implementation is made by Walied Othman, to contact me 
mail to Walied.Othman@Student.KULeuven.ac.be or 
Triade@ace.Ulyssis.Student.KULeuven.ac.be, 
always mention wether it 's about the FGInt for Delphi or for 
FreePascal, or wether it 's about the 6xs, preferably in the subject line. 
If you 're going to use these implementations, at least mention my 
name or something and notify me so I may even put a link on my page. 
This implementation is freeware and according to the coderpunks' 
manifesto it should remain so, so don 't use these implementations 
in commercial software.  Encryption, as a tool to ensure privacy 
should be free and accessible for anyone.  If you plan to use these 
implementations in a commercial application, contact me before 
doing so, that way you can license the software to use it in commercial 
Software.  If any algorithm is patented in your country, you should 
acquire a license before using this software.  Modified versions of this 
software must contain an acknowledgement of the original author (=me). 
This implementaion is available at 
http://ace.ulyssis.student.kuleuven.ac.be/~triade/ 
 
copyright 2000, Walied Othman 
This header may not be removed. 
} 
 
Unit FGInt; 
 
Interface 
 
Uses Windows, SysUtils, Controls, Math; 
 
Type 
   TCompare = (Lt, St, Eq, Er); 
   TSign = (negative, positive); 
   TFGInt = Record 
      Sign : TSign; 
      Number : Array Of int64; 
   End; 
 
Procedure zeronetochar8(Var g : char; Const x : String); 
Procedure zeronetochar6(Var g : integer; Const x : String); 
Procedure initialize8(Var trans : Array Of String); 
Procedure initialize6(Var trans : Array Of String); 
Procedure initialize6PGP(Var trans : Array Of String); 
Procedure ConvertBase256to64(Const str256 : String; Var str64 : String); 
Procedure ConvertBase64to256(Const str64 : String; Var str256 : String); 
Procedure ConvertBase256to2(Const str256 : String; Var str2 : String); 
Procedure ConvertBase64to2(Const str64 : String; Var str2 : String); 
Procedure ConvertBase2to256(str2 : String; Var str256 : String); 
Procedure ConvertBase2to64(str2 : String; Var str64 : String); 
Procedure ConvertBase256StringToHexString(Str256 : String; Var HexStr : String); 
Procedure ConvertHexStringToBase256String(HexStr : String; Var Str256 : String); 
Procedure PGPConvertBase256to64(Var str256, str64 : String); 
Procedure PGPConvertBase64to256(str64 : String; Var str256 : String); 
Procedure PGPConvertBase64to2(str64 : String; Var str2 : String); 
Procedure Base10StringToFGInt(Base10 : String; Var FGInt : TFGInt); 
Procedure FGIntToBase10String(Const FGInt : TFGInt; Var Base10 : String); 
Procedure FGIntDestroy(Var FGInt : TFGInt); 
Function FGIntCompareAbs(Const FGInt1, FGInt2 : TFGInt) : TCompare; 
Procedure FGIntAdd(Const FGInt1, FGInt2 : TFGInt; Var Sum : TFGInt); 
Procedure FGIntChangeSign(Var FGInt : TFGInt); 
Procedure FGIntSub(Var FGInt1, FGInt2, dif : TFGInt); 
Procedure FGIntMulByInt(Const FGInt : TFGInt; Var res : TFGInt; by : int64); 
Procedure FGIntMulByIntbis(Var FGInt : TFGInt; by : int64); 
Procedure FGIntDivByInt(Const FGInt : TFGInt; Var res : TFGInt; by : int64; Var modres : int64); 
Procedure FGIntDivByIntBis(Var FGInt : TFGInt; by : int64; Var modres : int64); 
Procedure FGIntModByInt(Const FGInt : TFGInt; by : int64; Var modres : int64); 
Procedure FGIntAbs(Var FGInt : TFGInt); 
Procedure FGIntCopy(Const FGInt1 : TFGInt; Var FGInt2 : TFGInt); 
Procedure FGIntShiftLeft(Var FGInt : TFGInt); 
Procedure FGIntShiftRight(Var FGInt : TFGInt); 
Procedure FGIntShiftRightBy31(Var FGInt : TFGInt); 
Procedure FGIntAddBis(Var FGInt1 : TFGInt; Const FGInt2 : TFGInt); 
Procedure FGIntSubBis(Var FGInt1 : TFGInt; Const FGInt2 : TFGInt); 
Procedure FGIntMul(Const FGInt1, FGInt2 : TFGInt; Var Prod : TFGInt); 
Procedure FGIntSquare(Const FGInt : TFGInt; Var Square : TFGInt); 
Procedure FGIntToBase2String(Const FGInt : TFGInt; Var S : String); 
Procedure Base2StringToFGInt(S : String; Var FGInt : TFGInt); 
Procedure FGIntToBase256String(Const FGInt : TFGInt; Var str256 : String); 
Procedure Base256StringToFGInt(str256 : String; Var FGInt : TFGInt); 
Procedure PGPMPIToFGInt(PGPMPI : String; Var FGInt : TFGInt); 
Procedure FGIntToPGPMPI(FGInt : TFGInt; Var PGPMPI : String); 
Procedure FGIntExp(Const FGInt, exp : TFGInt; Var res : TFGInt); 
Procedure FGIntFac(Const FGInt : TFGInt; Var res : TFGInt); 
Procedure FGIntShiftLeftBy31(Var FGInt : TFGInt); 
Procedure FGIntDivMod(Var FGInt1, FGInt2, QFGInt, MFGInt : TFGInt); 
Procedure FGIntDiv(Var FGInt1, FGInt2, QFGInt : TFGInt); 
Procedure FGIntMod(Var FGInt1, FGInt2, MFGInt : TFGInt); 
Procedure FGIntSquareMod(Var FGInt, Modb, FGIntSM : TFGInt); 
Procedure FGIntAddMod(Var FGInt1, FGInt2, base, FGIntres : TFGInt); 
Procedure FGIntMulMod(Var FGInt1, FGInt2, base, FGIntres : TFGInt); 
Procedure FGIntModExp(Var FGInt, exp, modb, res : TFGInt); 
Procedure FGIntModBis(Const FGInt : TFGInt; Var FGIntOut : TFGInt; b : longint; head : int64); 
Procedure FGIntMulModBis(Const FGInt1, FGInt2 : TFGInt; Var Prod : TFGInt; b : longint; head : int64); 
Procedure FGIntMontgomeryMod(Const GInt, base, baseInv : TFGInt; Var MGInt : TFGInt; b : longint; head : int64); 
Procedure FGIntMontgomeryModExp(Var FGInt, exp, modb, res : TFGInt); 
Procedure FGIntGCD(Const FGInt1, FGInt2 : TFGInt; Var GCD : TFGInt); 
Procedure FGIntLCM(Const FGInt1, FGInt2 : TFGInt; Var LCM : TFGInt); 
Procedure FGIntTrialDiv9999(Const FGInt : TFGInt; Var ok : boolean); 
Procedure FGIntRandom1(Var Seed, RandomFGInt : TFGInt); 
Procedure FGIntRabinMiller(Var FGIntp : TFGInt; nrtest : integer; Var ok : boolean); 
Procedure FGIntBezoutBachet(Var FGInt1, FGInt2, a, b : TFGInt); 
Procedure FGIntModInv(Const FGInt1, base : TFGInt; Var Inverse : TFGInt); 
Procedure FGIntPrimetest(Var FGIntp : TFGInt; nrRMtests : integer; Var ok : boolean); 
Procedure FGIntLegendreSymbol(Var a, p : TFGInt; Var L : integer); 
Procedure FGIntSquareRootModP(Square, Prime : TFGInt; Var SquareRoot : TFGInt); 
 
 
 
Implementation 
 
Var 
   primes : Array[1..1228] Of integer = 
      (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, 8209, 8219, 8221, 8231, 8233, 8237, 8243, 8263, 8269, 8273, 8287, 8291, 8293, 8297, 8311, 
      8317, 8329, 8353, 8363, 8369, 8377, 8387, 8389, 8419, 8423, 8429, 8431, 8443, 8447, 8461, 8467, 8501, 8513, 8521, 
      8527, 8537, 8539, 8543, 8563, 8573, 8581, 8597, 8599, 8609, 8623, 8627, 8629, 8641, 8647, 8663, 8669, 8677, 8681, 
      8689, 8693, 8699, 8707, 8713, 8719, 8731, 8737, 8741, 8747, 8753, 8761, 8779, 8783, 8803, 8807, 8819, 8821, 8831, 
      8837, 8839, 8849, 8861, 8863, 8867, 8887, 8893, 8923, 8929, 8933, 8941, 8951, 8963, 8969, 8971, 8999, 9001, 9007, 
      9011, 9013, 9029, 9041, 9043, 9049, 9059, 9067, 9091, 9103, 9109, 9127, 9133, 9137, 9151, 9157, 9161, 9173, 9181, 
      9187, 9199, 9203, 9209, 9221, 9227, 9239, 9241, 9257, 9277, 9281, 9283, 9293, 9311, 9319, 9323, 9337, 9341, 9343, 
      9349, 9371, 9377, 9391, 9397, 9403, 9413, 9419, 9421, 9431, 9433, 9437, 9439, 9461, 9463, 9467, 9473, 9479, 9491, 
      9497, 9511, 9521, 9533, 9539, 9547, 9551, 9587, 9601, 9613, 9619, 9623, 9629, 9631, 9643, 9649, 9661, 9677, 9679, 
      9689, 9697, 9719, 9721, 9733, 9739, 9743, 9749, 9767, 9769, 9781, 9787, 9791, 9803, 9811, 9817, 9829, 9833, 9839, 
      9851, 9857, 9859, 9871, 9883, 9887, 9901, 9907, 9923, 9929, 9931, 9941, 9949, 9967, 9973); 
   chr64 : Array[1..64] Of char = ('a', 'A', 'b', 'B', 'c', 'C', 'd', 'D', 'e', 'E', 'f', 'F', 
      'g', 'G', 'h', 'H', 'i', 'I', 'j', 'J', 'k', 'K', 'l', 'L', 'm', 'M', 'n', 'N', 'o', 'O', 'p', 
      'P', 'q', 'Q', 'r', 'R', 's', 'S', 't', 'T', 'u', 'U', 'v', 'V', 'w', 'W', 'x', 'X', 'y', 'Y', 
      'z', 'Z', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '+', '='); 
   PGPchr64 : Array[1..64] Of char = ('A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 
      'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z', 'a', 'b', 'c', 'd', 'e', 'f', 
      'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 
      'z', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '+', '/'); 
 
 
{$H+} 
 
 
Procedure zeronetochar8(Var g : char; Const x : String); 
Var 
   i : Integer; 
   b : byte; 
Begin 
   b := 0; 
   For i := 1 To 8 Do 
   Begin 
      If copy(x, i, 1) = '1' Then 
         b := b Or (1 Shl (8 - I)); 
   End; 
   g := chr(b); 
End; 
 
 
Procedure zeronetochar6(Var g : integer; Const x : String); 
Var 
   I : Integer; 
Begin 
   G := 0; 
   For I := 1 To Length(X) Do 
   Begin 
      If I > 6 Then 
         Break; 
      If X[I] <> '0' Then 
         G := G Or (1 Shl (6 - I)); 
   End; 
   Inc(G); 
End; 
 
 
Procedure initialize8(Var trans : Array Of String); 
Var 
   c1, c2, c3, c4, c5, c6, c7, c8 : integer; 
   x : String; 
   g : char; 
Begin 
   For c1 := 0 To 1 Do 
      For c2 := 0 To 1 Do 
         For c3 := 0 To 1 Do 
            For c4 := 0 To 1 Do 
               For c5 := 0 To 1 Do 
                  For c6 := 0 To 1 Do 
                     For c7 := 0 To 1 Do 
                        For c8 := 0 To 1 Do 
                        Begin 
                           x := ''; 
                           x := inttostr(c1) + inttostr(c2) + inttostr(c3) + inttostr(c4) + inttostr(c5) + inttostr(c6) + inttostr(c7) + inttostr(c8); 
                           zeronetochar8(g, x); 
                           trans[ord(g)] := x; 
                        End; 
End; 
 
 
Procedure initialize6(Var trans : Array Of String); 
Var 
   c1, c2, c3, c4, c5, c6 : integer; 
   x : String; 
   g : integer; 
Begin 
   For c1 := 0 To 1 Do 
      For c2 := 0 To 1 Do 
         For c3 := 0 To 1 Do 
            For c4 := 0 To 1 Do 
               For c5 := 0 To 1 Do 
                  For c6 := 0 To 1 Do 
                  Begin 
                     x := ''; 
                     x := inttostr(c1) + inttostr(c2) + inttostr(c3) + inttostr(c4) + inttostr(c5) + inttostr(c6); 
                     zeronetochar6(g, x); 
                     trans[ord(chr64[g])] := x; 
                  End; 
End; 
 
Procedure initialize6PGP(Var trans : Array Of String); 
Var 
   c1, c2, c3, c4, c5, c6 : integer; 
   x : String; 
   g : integer; 
Begin 
   For c1 := 0 To 1 Do 
      For c2 := 0 To 1 Do 
         For c3 := 0 To 1 Do 
            For c4 := 0 To 1 Do 
               For c5 := 0 To 1 Do 
                  For c6 := 0 To 1 Do 
                  Begin 
                     x := ''; 
                     x := inttostr(c1) + inttostr(c2) + inttostr(c3) + inttostr(c4) + inttostr(c5) + inttostr(c6); 
                     zeronetochar6(g, x); 
                     trans[ord(PGPchr64[g])] := x; 
                  End; 
End; 
 
 
// Convert base 8 strings to base 6 strings and visa versa 
 
Procedure ConvertBase256to64(Const str256 : String; Var str64 : String); 
Var 
   temp : String; 
   trans : Array[0..255] Of String; 
   i, len6 : longint; 
   g : integer; 
Begin 
   initialize8(trans); 
   temp := ''; 
   For i := 1 To length(str256) Do temp := temp + trans[ord(str256[i])]; 
   While (length(temp) Mod 6) <> 0 Do temp := temp + '0'; 
   len6 := length(temp) Div 6; 
   str64 := ''; 
   For i := 1 To len6 Do 
   Begin 
      zeronetochar6(g, copy(temp, 1, 6)); 
      str64 := str64 + chr64[g]; 
      delete(temp, 1, 6); 
   End; 
End; 
 
 
Procedure ConvertBase64to256(Const str64 : String; Var str256 : String); 
Var 
   temp : String; 
   trans : Array[0..255] Of String; 
   i, len8 : longint; 
   g : char; 
Begin 
   initialize6(trans); 
   temp := ''; 
   For i := 1 To length(str64) Do temp := temp + trans[ord(str64[i])]; 
   str256 := ''; 
   len8 := length(temp) Div 8; 
   For i := 1 To len8 Do 
   Begin 
      zeronetochar8(g, copy(temp, 1, 8)); 
      str256 := str256 + g; 
      delete(temp, 1, 8); 
   End; 
End; 
 
 
// Convert base 8 & 6 bit strings to base 2 strings and visa versa 
 
Procedure ConvertBase256to2(Const str256 : String; Var str2 : String); 
Var 
   trans : Array[0..255] Of String; 
   i : longint; 
Begin 
   str2 := ''; 
   initialize8(trans); 
   For i := 1 To length(str256) Do str2 := str2 + trans[ord(str256[i])]; 
End; 
 
 
Procedure ConvertBase64to2(Const str64 : String; Var str2 : String); 
Var 
   trans : Array[0..255] Of String; 
   i : longint; 
Begin 
   str2 := ''; 
   initialize6(trans); 
   For i := 1 To length(str64) Do str2 := str2 + trans[ord(str64[i])]; 
End; 
 
 
Procedure ConvertBase2to256(str2 : String; Var str256 : String); 
Var 
   i, len8 : longint; 
   g : char; 
Begin 
   str256 := ''; 
   While (length(str2) Mod 8) <> 0 Do str2 := '0' + str2; 
   len8 := length(str2) Div 8; 
   For i := 1 To len8 Do 
   Begin 
      zeronetochar8(g, copy(str2, 1, 8)); 
      str256 := str256 + g; 
      delete(str2, 1, 8); 
   End; 
End; 
 
 
Procedure ConvertBase2to64(str2 : String; Var str64 : String); 
Var 
   i, len6 : longint; 
   g : integer; 
Begin 
   str64 := ''; 
   While (length(str2) Mod 6) <> 0 Do str2 := '0' + str2; 
   len6 := length(str2) Div 6; 
   For i := 1 To len6 Do 
   Begin 
      zeronetochar6(g, copy(str2, 1, 6)); 
      str64 := str64 + chr64[g]; 
      delete(str2, 1, 6); 
   End; 
End; 
 
 
// Convert base 256 strings to base 16 (HexaDecimal) strings and visa versa 
 
Procedure ConvertBase256StringToHexString(Str256 : String; Var HexStr : String); 
Var 
   i : longint; 
   b : byte; 
Begin 
   HexStr := ''; 
   For i := 1 To length(str256) Do 
   Begin 
      b := ord(str256[i]); 
      If (b Shr 4) < 10 Then HexStr := HexStr + chr(48 + (b Shr 4)) 
      Else HexStr := HexStr + chr(55 + (b Shr 4)); 
      If (b And 15) < 10 Then HexStr := HexStr + chr(48 + (b And 15)) 
      Else HexStr := HexStr + chr(55 + (b And 15)); 
   End; 
End; 
 
 
Procedure ConvertHexStringToBase256String(HexStr : String; Var Str256 : String); 
Var 
   i : longint; 
   b, h1, h2 : byte; 
Begin 
   Str256 := ''; 
   For i := 1 To (length(Hexstr) Div 2) Do 
   Begin 
      h2 := ord(HexStr[2 * i]); 
      h1 := ord(HexStr[2 * i - 1]); 
      If h1 < 58 Then b := ((h1 - 48) Shl 4) Else b := ((h1 - 55) Shl 4); 
      If h2 < 58 Then b := (b Or (h2 - 48)) Else b := (b Or (h2 - 55)); 
      Str256 := Str256 + chr(b); 
   End; 
End; 
 
 
// Convert base 256 strings to base 64 strings and visa versa, PGP style 
 
Procedure PGPConvertBase256to64(Var str256, str64 : String); 
Var 
   temp, x, a : String; 
   i, len6 : longint; 
   g : integer; 
   trans : Array[0..255] Of String; 
Begin 
   initialize8(trans); 
   temp := ''; 
   For i := 1 To length(str256) Do temp := temp + trans[ord(str256[i])]; 
   If (length(temp) Mod 6) = 0 Then a := '' Else 
      If (length(temp) Mod 6) = 4 Then 
      Begin 
         temp := temp + '00'; 
         a := '=' 
      End 
      Else 
      Begin 
         temp := temp + '0000'; 
         a := '==' 
      End; 
   str64 := ''; 
   len6 := length(temp) Div 6; 
   For i := 1 To len6 Do 
   Begin 
      x := copy(temp, 1, 6); 
      zeronetochar6(g, x); 
      str64 := str64 + PGPchr64[g]; 
      delete(temp, 1, 6); 
   End; 
   str64 := str64 + a; 
End; 
 
 
Procedure PGPConvertBase64to256(str64 : String; Var str256 : String); 
Var 
   temp, x : String; 
   i, j, len8 : longint; 
   g : char; 
   trans : Array[0..255] Of String; 
Begin 
   initialize6PGP(trans); 
   temp := ''; 
   str256 := ''; 
   If str64[length(str64) - 1] = '=' Then j := 2 Else 
      If str64[length(str64)] = '=' Then j := 1 Else j := 0; 
   For i := 1 To (length(str64) - j) Do temp := temp + trans[ord(str64[i])]; 
   If j <> 0 Then delete(temp, length(temp) - 2 * j + 1, 2 * j); 
   len8 := length(temp) Div 8; 
   For i := 1 To len8 Do 
   Begin 
      x := copy(temp, 1, 8); 
      zeronetochar8(g, x); 
      str256 := str256 + g; 
      delete(temp, 1, 8); 
   End; 
End; 
 
// Convert base 64 strings to base 2 strings, PGP style 
 
 
Procedure PGPConvertBase64to2(str64 : String; Var str2 : String); 
Var 
   i, j : longint; 
   trans : Array[0..255] Of String; 
Begin 
   str2 := ''; 
   initialize6(trans); 
   If str64[length(str64) - 1] = '=' Then j := 2 Else 
      If str64[length(str64)] = '=' Then j := 1 Else j := 0; 
   For i := 1 To (length(str64) - j) Do str2 := str2 + trans[ord(str64[i])]; 
   delete(str2, length(str2) - 2 * j + 1, 2 * j); 
End; 
 
 
// Convert a base 10 string to a FGInt 
 
Procedure Base10StringToFGInt(Base10 : String; Var FGInt : TFGInt); 
Var 
   i, size : longint; 
   j : int64; 
   S : String; 
   sign : TSign; 
 
   Procedure GIntDivByIntBis1(Var GInt : TFGInt; by : int64; Var modres : int64); 
   Var 
      i, size : longint; 
      rest : int64; 
   Begin 
      size := GInt.Number[0]; 
      modres := 0; 
      For i := size Downto 1 Do 
      Begin 
         modres := modres * 1000000000; 
         rest := modres + GInt.Number[i]; 
         GInt.Number[i] := rest Div by; 
         modres := rest Mod by; 
      End; 
      While (GInt.Number[size] = 0) And (size > 1) Do size := size - 1; 
      If size <> GInt.Number[0] Then 
      Begin 
         SetLength(GInt.Number, size + 1); 
         GInt.Number[0] := size; 
      End; 
   End; 
 
Begin 
   While (Not (Base10[1] In ['-', '0'..'9'])) And (length(Base10) > 1) Do 
      delete(Base10, 1, 1); 
   If copy(Base10, 1, 1) = '-' Then 
   Begin 
      Sign := negative; 
      delete(Base10, 1, 1); 
   End 
   Else Sign := positive; 
   While (length(Base10) > 1) And (copy(Base10, 1, 1) = '0') Do delete(Base10, 1, 1); 
   size := length(Base10) Div 9; 
   If (length(Base10) Mod 9) <> 0 Then size := size + 1; 
   SetLength(FGInt.Number, size + 1); 
   FGInt.Number[0] := size; 
   For i := 1 To size - 1 Do 
   Begin 
      FGInt.Number[i] := StrToInt(copy(Base10, length(Base10) - 8, 9)); 
      delete(Base10, length(Base10) - 8, 9); 
   End; 
   FGInt.Number[size] := StrToInt(Base10); 
 
   S := ''; 
   While (FGInt.Number[0] <> 1) Or (FGInt.Number[1] <> 0) Do 
   Begin 
      GIntDivByIntBis1(FGInt, 2, j); 
      S := inttostr(j) + S; 
   End; 
   S := '0' + S; 
   FGIntDestroy(FGInt); 
   Base2StringToFGInt(S, FGInt); 
   FGInt.Sign := sign; 
End; 
 
 
// Convert a FGInt to a base 10 string 
 
Procedure FGIntToBase10String(Const FGInt : TFGInt; Var Base10 : String); 
Var 
   S : String; 
   j : int64; 
   temp : TFGInt; 
Begin 
   FGIntCopy(FGInt, temp); 
   Base10 := ''; 
   While (temp.Number[0] > 1) Or (temp.Number[1] > 0) Do 
   Begin 
      FGIntDivByIntBis(temp, 1000000000, j); 
      S := IntToStr(j); 
      While Length(S) < 9 Do S := '0' + S; 
      Base10 := S + Base10; 
   End; 
   Base10 := '0' + Base10; 
   While (length(Base10) > 1) And (Base10[1] = '0') Do delete(Base10, 1, 1); 
   If FGInt.Sign = negative Then Base10 := '-' + Base10; 
End; 
 
 
 
// Destroy a FGInt to free memory 
 
Procedure FGIntDestroy(Var FGInt : TFGInt); 
Begin 
   FGInt.Number := Nil; 
End; 
 
 
// Compare 2 FGInts in absolute value, returns 
// Lt if FGInt1 > FGInt2, St if FGInt1 < FGInt2, Eq if FGInt1 = FGInt2, 
// Er otherwise 
 
Function FGIntCompareAbs(Const FGInt1, FGInt2 : TFGInt) : TCompare; 
Var 
   size1, size2, i : longint; 
Begin 
   FGIntCompareAbs := Er; 
   size1 := FGInt1.Number[0]; 
   size2 := FGInt2.Number[0]; 
   If size1 > size2 Then FGIntCompareAbs := Lt Else 
      If size1 < size2 Then FGIntCompareAbs := St Else 
      Begin 
         i := size2; 
         While (FGInt1.Number[i] = FGInt2.Number[i]) And (i > 1) Do i := i - 1; 
         If FGInt1.Number[i] = FGInt2.Number[i] Then FGIntCompareAbs := Eq Else 
            If FGInt1.Number[i] < FGInt2.Number[i] Then FGIntCompareAbs := St Else 
               If FGInt1.Number[i] > FGInt2.Number[i] Then FGIntCompareAbs := Lt; 
      End; 
End; 
 
 
// Add 2 FGInts, FGInt1 + FGInt2 = Sum 
 
Procedure FGIntAdd(Const FGInt1, FGInt2 : TFGInt; Var Sum : TFGInt); 
Var 
   i, size1, size2, size : longint; 
   rest : integer; 
   Trest : int64; 
Begin 
   size1 := FGInt1.Number[0]; 
   size2 := FGInt2.Number[0]; 
   If size1 < size2 Then FGIntAdd(FGInt2, FGInt1, Sum) Else 
   Begin 
      If FGInt1.Sign = FGInt2.Sign Then 
      Begin 
         Sum.Sign := FGInt1.Sign; 
         SetLength(Sum.Number, size1 + 2); 
         rest := 0; 
         For i := 1 To size2 Do 
         Begin 
            Trest := FGInt1.Number[i] + FGInt2.Number[i] + rest; 
            Sum.Number[i] := Trest And 2147483647; 
            rest := Trest Shr 31; 
         End; 
         For i := (size2 + 1) To size1 Do 
         Begin 
            Trest := FGInt1.Number[i] + rest; 
            Sum.Number[i] := Trest And 2147483647; 
            rest := Trest Shr 31; 
         End; 
         size := size1 + 1; 
         Sum.Number[0] := size; 
         Sum.Number[size] := rest; 
         While (Sum.Number[size] = 0) And (size > 1) Do size := size - 1; 
         If Sum.Number[0] > size Then SetLength(Sum.Number, size + 1); 
         Sum.Number[0] := size; 
      End 
      Else 
      Begin 
         If FGIntCompareAbs(FGInt2, FGInt1) = Lt Then FGIntAdd(FGInt2, FGInt1, Sum) 
         Else 
         Begin 
            SetLength(Sum.Number, size1 + 1); 
            rest := 0; 
            For i := 1 To size2 Do 
            Begin 
               Trest := 2147483648 + FGInt1.Number[i] - FGInt2.Number[i] + rest; 
               Sum.Number[i] := Trest And 2147483647; 
               If (Trest > 2147483647) Then rest := 0 Else rest := -1; 
            End; 
            For i := (size2 + 1) To size1 Do 
            Begin 
               Trest := 2147483648 + FGInt1.Number[i] + rest; 
               Sum.Number[i] := Trest And 2147483647; 
               If (Trest > 2147483647) Then rest := 0 Else rest := -1; 
            End; 
            size := size1; 
            While (Sum.Number[size] = 0) And (size > 1) Do size := size - 1; 
            If size < size1 Then 
            Begin 
               SetLength(Sum.Number, size + 1); 
            End; 
            Sum.Number[0] := size; 
            Sum.Sign := FGInt1.Sign; 
         End; 
      End; 
   End; 
End; 
 
 
Procedure FGIntChangeSign(Var FGInt : TFGInt); 
Begin 
   If FGInt.Sign = negative Then FGInt.Sign := positive Else FGInt.Sign := negative; 
End; 
 
 
// Substract 2 FGInts, FGInt1 - FGInt2 = dif 
 
Procedure FGIntSub(Var FGInt1, FGInt2, dif : TFGInt); 
Begin 
   FGIntChangeSign(FGInt2); 
   FGIntAdd(FGInt1, FGInt2, dif); 
   FGIntChangeSign(FGInt2); 
End; 
 
 
// multiply a FGInt by an integer, FGInt * by = res, by < 1000000000 
 
Procedure FGIntMulByInt(Const FGInt : TFGInt; Var res : TFGInt; by : int64); 
Var 
   i, size : longint; 
   Trest, rest : int64; 
Begin 
   size := FGInt.Number[0]; 
   SetLength(res.Number, size + 2); 
   rest := 0; 
   For i := 1 To size Do 
   Begin 
      Trest := FGInt.Number[i] * by + rest; 
      res.Number[i] := Trest And 2147483647; 
      rest := Trest Shr 31; 
   End; 
   If rest <> 0 Then 
   Begin 
      size := size + 1; 
      Res.Number[size] := rest; 
   End 
   Else SetLength(Res.Number, size + 1); 
   Res.Number[0] := size; 
   Res.Sign := FGInt.Sign; 
End; 
 
 
// multiply a FGInt by an integer, FGInt * by = res, by < 1000000000 
 
Procedure FGIntMulByIntbis(Var FGInt : TFGInt; by : int64); 
Var 
   i, size : longint; 
   Trest, rest : int64; 
Begin 
   size := FGInt.Number[0]; 
   SetLength(FGInt.Number, size + 2); 
   rest := 0; 
   For i := 1 To size Do 
   Begin 
      Trest := FGInt.Number[i] * by + rest; 
      FGInt.Number[i] := Trest And 2147483647; 
      rest := Trest Shr 31; 
   End; 
   If rest <> 0 Then 
   Begin 
      size := size + 1; 
      FGInt.Number[size] := rest; 
   End 
   Else SetLength(FGInt.Number, size + 1); 
   FGInt.Number[0] := size; 
End; 
 
 
// divide a FGInt by an integer, FGInt = res * by + modres 
 
Procedure FGIntDivByInt(Const FGInt : TFGInt; Var res : TFGInt; by : int64; Var modres : int64); 
Var 
   i, size : longint; 
   rest : int64; 
Begin 
   size := FGInt.Number[0]; 
   SetLength(res.Number, size + 1); 
   modres := 0; 
   For i := size Downto 1 Do 
   Begin 
      modres := modres Shl 31; 
      rest := modres Or FGInt.Number[i]; 
      res.Number[i] := rest Div by; 
      modres := rest Mod by; 
   End; 
   While (res.Number[size] = 0) And (size > 1) Do size := size - 1; 
   SetLength(res.Number, size + 1); 
   res.Number[0] := size; 
   Res.Sign := FGInt.Sign; 
End; 
 
 
// divide a FGInt by an integer, FGInt = FGInt * by + modres 
 
Procedure FGIntDivByIntBis(Var FGInt : TFGInt; by : int64; Var modres : int64); 
Var 
   i, size : longint; 
   rest : int64; 
Begin 
   size := FGInt.Number[0]; 
   modres := 0; 
   For i := size Downto 1 Do 
   Begin 
      modres := modres Shl 31; 
      rest := modres Or FGInt.Number[i]; 
      FGInt.Number[i] := rest Div by; 
      modres := rest Mod by; 
   End; 
   While (FGInt.Number[size] = 0) And (size > 1) Do size := size - 1; 
   If size <> FGInt.Number[0] Then 
   Begin 
      SetLength(FGInt.Number, size + 1); 
      FGInt.Number[0] := size; 
   End; 
End; 
 
 
// Reduce a FGInt modulo by (=an integer), FGInt mod by = modres 
 
Procedure FGIntModByInt(Const FGInt : TFGInt; by : int64; Var modres : int64); 
Var 
   i, size : longint; 
   rest : int64; 
Begin 
   size := FGInt.Number[0]; 
   modres := 0; 
   For i := size Downto 1 Do 
   Begin 
      modres := modres Shl 31; 
      rest := modres + FGInt.Number[i]; 
      modres := rest Mod by; 
   End; 
End; 
 
 
// Returns the FGInt in absolute value 
 
Procedure FGIntAbs(Var FGInt : TFGInt); 
Begin 
   FGInt.Sign := positive; 
End; 
 
 
// Copy a FGInt1 into FGInt2 
 
Procedure FGIntCopy(Const FGInt1 : TFGInt; Var FGInt2 : TFGInt); 
Begin 
   FGInt2.Sign := FGInt1.Sign; 
   FGInt2.Number := Nil; 
   FGInt2.Number := Copy(FGInt1.Number, 0, FGInt1.Number[0] + 1); 
End; 
 
 
// Shift the FGInt to the left in base 2 notation, ie FGInt = FGInt * 2 
 
Procedure FGIntShiftLeft(Var FGInt : TFGInt); 
Var 
   l, m : int64; 
   i, size : longint; 
Begin 
   size := FGInt.Number[0]; 
   l := 0; 
   For i := 1 To Size Do 
   Begin 
      m := FGInt.Number[i] Shr 30; 
      FGInt.Number[i] := ((FGInt.Number[i] Shl 1) Or l) And 2147483647; 
      l := m; 
   End; 
   If l <> 0 Then 
   Begin 
      setlength(FGInt.Number, size + 2); 
      FGInt.Number[size + 1] := l; 
      FGInt.Number[0] := size + 1; 
   End; 
End; 
 
 
// Shift the FGInt to the right in base 2 notation, ie FGInt = FGInt div 2 
 
Procedure FGIntShiftRight(Var FGInt : TFGInt); 
Var 
   l, m : int64; 
   i, size : longint; 
Begin 
   size := FGInt.Number[0]; 
   l := 0; 
   For i := size Downto 1 Do 
   Begin 
      m := FGInt.Number[i] And 1; 
      FGInt.Number[i] := (FGInt.Number[i] Shr 1) Or l; 
      l := m Shl 30; 
   End; 
   If (FGInt.Number[size] = 0) And (size > 1) Then 
   Begin 
      setlength(FGInt.Number, size); 
      FGInt.Number[0] := size - 1; 
   End; 
End; 
 
 
// FGInt = FGInt / 2147483648 
 
Procedure FGIntShiftRightBy31(Var FGInt : TFGInt); 
Var 
   size : longint; 
Begin 
   size := FGInt.Number[0]; 
   If size > 1 Then 
   Begin 
      FGInt.Number := Copy(FGInt.Number, 1, Size); 
      FGInt.Number[0] := size - 1; 
   End 
   Else FGInt.Number[1] := 0; 
End; 
 
 
// FGInt1 = FGInt1 + FGInt2, FGInt1 > FGInt2 
 
Procedure FGIntAddBis(Var FGInt1 : TFGInt; Const FGInt2 : TFGInt); 
Var 
   i, size1, size2 : longint; 
   rest : integer; 
   Trest : int64; 
Begin 
   size1 := FGInt1.Number[0]; 
   size2 := FGInt2.Number[0]; 
   rest := 0; 
   For i := 1 To size2 Do 
   Begin 
      Trest := FGInt1.Number[i] + FGInt2.Number[i] + rest; 
      rest := Trest Shr 31; 
      FGInt1.Number[i] := Trest And 2147483647; 
   End; 
   For i := size2 + 1 To size1 Do 
   Begin 
      Trest := FGInt1.Number[i] + rest; 
      rest := Trest Shr 31; 
      FGInt1.Number[i] := Trest And 2147483647; 
   End; 
   If rest <> 0 Then 
   Begin 
      SetLength(FGInt1.Number, size1 + 2); 
      FGInt1.Number[0] := size1 + 1; 
      FGInt1.Number[size1 + 1] := rest; 
   End; 
End; 
 
 
// FGInt1 = FGInt1 - FGInt2, use only when 0 < FGInt2 < FGInt1 
 
Procedure FGIntSubBis(Var FGInt1 : TFGInt; Const FGInt2 : TFGInt); 
Var 
   i, size1, size2 : longint; 
   rest : integer; 
   Trest : int64; 
Begin 
   size1 := FGInt1.Number[0]; 
   size2 := FGInt2.Number[0]; 
   rest := 0; 
   For i := 1 To size2 Do 
   Begin 
      Trest := 2147483648 + FGInt1.Number[i] - FGInt2.Number[i] + rest; 
      If (Trest > 2147483647) Then rest := 0 Else rest := -1; 
      FGInt1.Number[i] := Trest And 2147483647; 
   End; 
   For i := size2 + 1 To size1 Do 
   Begin 
      Trest := 2147483648 + FGInt1.Number[i] + rest; 
      If (Trest > 2147483647) Then rest := 0 Else rest := -1; 
      FGInt1.Number[i] := Trest And 2147483647; 
   End; 
   i := size1; 
   While (FGInt1.Number[i] = 0) And (i > 1) Do i := i - 1; 
   If i < size1 Then 
   Begin 
      SetLength(FGInt1.Number, i + 1); 
      FGInt1.Number[0] := i; 
   End; 
End; 
 
 
// Multiply 2 FGInts, FGInt1 * FGInt2 = Prod 
 
Procedure FGIntMul(Const FGInt1, FGInt2 : TFGInt; Var Prod : TFGInt); 
Var 
   i, j, size, size1, size2 : longint; 
   rest, Trest : int64; 
Begin 
   size1 := FGInt1.Number[0]; 
   size2 := FGInt2.Number[0]; 
   size := size1 + size2; 
   SetLength(Prod.Number, size + 1); 
   For i := 1 To size Do Prod.Number[i] := 0; 
 
   For i := 1 To size2 Do 
   Begin 
      rest := 0; 
      For j := 1 To size1 Do 
      Begin 
         Trest := Prod.Number[j + i - 1] + FGInt1.Number[j] * FGInt2.Number[i] + rest; 
         Prod.Number[j + i - 1] := Trest And 2147483647; 
         rest := Trest Shr 31; 
      End; 
      Prod.Number[i + size1] := rest; 
   End; 
 
   Prod.Number[0] := size; 
   While (Prod.Number[size] = 0) And (size > 1) Do size := size - 1; 
   If size < Prod.Number[0] Then 
   Begin 
      SetLength(Prod.Number, size + 1); 
      Prod.Number[0] := size; 
   End; 
   If FGInt1.Sign = FGInt2.Sign Then Prod.Sign := Positive Else prod.Sign := negative; 
End; 
 
 
// Square a FGInt, FGInt² = Square 
 
Procedure FGIntSquare(Const FGInt : TFGInt; Var Square : TFGInt); 
Var 
   size, size1, i, j : longint; 
   rest, Trest : int64; 
Begin 
   size1 := FGInt.Number[0]; 
   size := 2 * size1; 
   SetLength(Square.Number, size + 1); 
   Square.Number[0] := size; 
   For i := 1 To size Do Square.Number[i] := 0; 
   For i := 1 To size1 Do 
   Begin 
      Trest := Square.Number[2 * i - 1] + FGInt.Number[i] * FGInt.Number[i]; 
      Square.Number[2 * i - 1] := Trest And 2147483647; 
      rest := Trest Shr 31; 
      For j := i + 1 To size1 Do 
      Begin 
         Trest := Square.Number[i + j - 1] + 2 * FGInt.Number[i] * FGInt.Number[j] + rest; 
         Square.Number[i + j - 1] := Trest And 2147483647; 
         rest := Trest Shr 31; 
      End; 
      Square.Number[i + size1] := rest; 
   End; 
   Square.Sign := positive; 
   While (Square.Number[size] = 0) And (size > 1) Do size := size - 1; 
   If size < 2 * size1 Then 
   Begin 
      SetLength(Square.Number, size + 1); 
      Square.Number[0] := size; 
   End; 
End; 
 
 
// Convert a FGInt to a binary string (base 2) & visa versa 
 
Procedure FGIntToBase2String(Const FGInt : TFGInt; Var S : String); 
Var 
   i : longint; 
   j : integer; 
Begin 
   S := ''; 
   For i := 1 To FGInt.Number[0] Do 
   Begin 
      For j := 0 To 30 Do S := inttostr(1 And (FGInt.Number[i] Shr j)) + S; 
   End; 
   While (length(S) > 1) And (S[1] = '0') Do delete(S, 1, 1); 
   If S = '' Then S := '0'; 
End; 
 
 
Procedure Base2StringToFGInt(S : String; Var FGInt : TFGInt); 
Var 
   i, j, size : longint; 
Begin 
   while (S[1]='0') and (length(S)>1) do delete(S,1,1); 
   size := length(S) Div 31; 
   If (length(S) Mod 31) <> 0 Then size := size + 1; 
   SetLength(FGInt.Number, size + 1); 
   FGInt.Number[0] := size; 
   j := 1; 
   FGInt.Number[j] := 0; 
   i := 0; 
   While length(S) > 0 Do 
   Begin 
      If S[length(S)] = '1' Then 
         FGInt.Number[j] := FGInt.Number[j] Or (1 Shl i); 
      i := i + 1; 
      If i = 31 Then 
      Begin 
         i := 0; 
         j := j + 1; 
         If j <= size Then FGInt.Number[j] := 0; 
      End; 
      delete(S, length(S), 1); 
   End; 
   FGInt.Sign := positive; 
End; 
 
 
// Convert a FGInt to an base 256 string & visa versa 
 
Procedure FGIntToBase256String(Const FGInt : TFGInt; Var str256 : String); 
Var 
   temp1 : String; 
   i, len8 : longint; 
   g : char; 
Begin 
   FGIntToBase2String(FGInt, temp1); 
   While (length(temp1) Mod 8) <> 0 Do temp1 := '0' + temp1; 
   len8 := length(temp1) Div 8; 
   str256 := ''; 
   For i := 1 To len8 Do 
   Begin 
      zeronetochar8(g, copy(temp1, 1, 8)); 
      str256 := str256 + g; 
      delete(temp1, 1, 8); 
   End; 
End; 
 
 
Procedure Base256StringToFGInt(str256 : String; Var FGInt : TFGInt); 
Var 
   temp1 : String; 
   i : longint; 
   trans : Array[0..255] Of String; 
Begin 
   temp1 := ''; 
   initialize8(trans); 
   For i := 1 To length(str256) Do temp1 := temp1 + trans[ord(str256[i])]; 
   While (temp1[1] = '0') And (temp1 <> '0') Do delete(temp1, 1, 1); 
   Base2StringToFGInt(temp1, FGInt); 
End; 
 
// Convert an MPI (Multiple Precision Integer, PGP style) to an FGInt & 
// visa versa 
 
Procedure PGPMPIToFGInt(PGPMPI : String; Var FGInt : TFGInt); 
Var 
   temp : String; 
Begin 
   temp := PGPMPI; 
   delete(temp, 1, 2); 
   Base256StringToFGInt(temp, FGInt); 
End; 
 
 
Procedure FGIntToPGPMPI(FGInt : TFGInt; Var PGPMPI : String); 
Var 
   len, i : word; 
   c : char; 
   b : byte; 
Begin 
   FGIntToBase256String(FGInt, PGPMPI); 
   len := length(PGPMPI) * 8; 
   c := PGPMPI[1]; 
   For i := 7 Downto 0 Do If (ord(c) Shr i) = 0 Then len := len - 1 Else break; 
   b := len Mod 256; 
   PGPMPI := chr(b) + PGPMPI; 
   b := len Div 256; 
   PGPMPI := chr(b) + PGPMPI; 
End; 
 
 
// Exponentiate a FGInt, FGInt^exp = res 
 
Procedure FGIntExp(Const FGInt, exp : TFGInt; Var res : TFGInt); 
Var 
   temp2, temp3 : TFGInt; 
   S : String; 
   i : longint; 
Begin 
   FGIntToBase2String(exp, S); 
   If S[length(S)] = '0' Then Base10StringToFGInt('1', res) Else FGIntCopy(FGInt, res); 
   FGIntCopy(FGInt, temp2); 
   If length(S) > 1 Then 
      For i := (length(S) - 1) Downto 1 Do 
      Begin 
         FGIntSquare(temp2, temp3); 
         FGIntCopy(temp3, temp2); 
         If S[i] = '1' Then 
         Begin 
            FGIntMul(res, temp2, temp3); 
            FGIntCopy(temp3, res); 
         End; 
      End; 
End; 
 
 
// Compute FGInt! = FGInt * (FGInt - 1) * (FGInt - 2) * ... * 3 * 2 * 1 
 
Procedure FGIntFac(Const FGInt : TFGInt; Var res : TFGInt); 
Var 
   one, temp, temp1 : TFGInt; 
Begin 
   FGIntCopy(FGInt, temp); 
   Base10StringToFGInt('1', res); 
   Base10StringToFGInt('1', one); 
 
   While Not (FGIntCompareAbs(temp, one) = Eq) Do 
   Begin 
      FGIntMul(temp, res, temp1); 
      FGIntCopy(temp1, res); 
      FGIntSubBis(temp, one); 
   End; 
 
   FGIntDestroy(one); 
   FGIntDestroy(temp); 
End; 
 
 
// FGInt = FGInt * 2147483648 
 
Procedure FGIntShiftLeftBy31(Var FGInt : TFGInt); 
Var 
   f1, f2 : int64; 
   i, size : longint; 
Begin 
   size := FGInt.Number[0]; 
   SetLength(FGInt.Number, size + 2); 
   f1 := 0; 
   For i := 1 To (size + 1) Do 
   Begin 
      f2 := FGInt.Number[i]; 
      FGInt.Number[i] := f1; 
      f1 := f2; 
   End; 
   FGInt.Number[0] := size + 1; 
End; 
 
 
// Divide 2 FGInts, FGInt1 = FGInt2 * QFGInt + MFGInt, MFGInt is always positive 
 
Procedure FGIntDivMod(Var FGInt1, FGInt2, QFGInt, MFGInt : TFGInt); 
Var 
   one, zero, temp1, temp2 : TFGInt; 
   s1, s2 : TSign; 
   i, j, s, t : longint; 
Begin 
   s1 := FGInt1.Sign; 
   s2 := FGInt2.Sign; 
   FGIntAbs(FGInt1); 
   FGIntAbs(FGInt2); 
   FGIntCopy(FGInt1, MFGInt); 
   FGIntCopy(FGInt2, temp1); 
 
   If FGIntCompareAbs(FGInt1, FGInt2) <> St Then 
   Begin 
      s := FGInt1.Number[0] - FGInt2.Number[0]; 
      setlength(QFGInt.Number, s + 2); 
      QFGInt.Number[0] := s + 1; 
      For t := 1 To s Do 
      Begin 
         FGIntShiftLeftBy31(temp1); 
         QFGInt.Number[t] := 0; 
      End; 
      j := s + 1; 
      QFGInt.Number[j] := 0; 
      While FGIntCompareAbs(MFGInt, FGInt2) <> St Do 
      Begin 
         While FGIntCompareAbs(MFGInt, temp1) <> St Do 
         Begin 
            If MFGInt.Number[0] > temp1.Number[0] Then 
               i := (2147483648 * MFGInt.Number[MFGInt.Number[0]] + MFGInt.Number[MFGInt.Number[0] - 1]) Div (temp1.Number[temp1.Number[0]] + 1) 
            Else i := MFGInt.Number[MFGInt.Number[0]] Div (temp1.Number[temp1.Number[0]] + 1); 
            If (i <> 0) Then 
            Begin 
               FGIntCopy(temp1, temp2); 
               FGIntMulByIntBis(temp2, i); 
               FGIntSubBis(MFGInt, temp2); 
               QFGInt.Number[j] := QFGInt.Number[j] + i; 
               If FGIntCompareAbs(MFGInt, temp2) <> St Then 
               Begin 
                  QFGInt.Number[j] := QFGInt.Number[j] + i; 
                  FGIntSubBis(MFGInt, temp2); 
               End; 
            End Else 
            Begin 
               QFGInt.Number[j] := QFGInt.Number[j] + 1; 
               FGIntSubBis(MFGInt, temp1); 
            End; 
         End; 
         If MFGInt.Number[0] <= temp1.Number[0] Then 
            If FGIntCompareAbs(temp1, FGInt2) <> Eq Then 
            Begin 
               FGIntShiftRightBy31(temp1); 
               j := j - 1; 
            End; 
      End; 
   End 
   Else Base10StringToFGInt('0', QFGInt); 
   s := QFGInt.Number[0]; 
   While (s > 1) And (QFGInt.Number[s] = 0) Do s := s - 1; 
   If s < QFGInt.Number[0] Then 
   Begin 
      setlength(QFGInt.Number, s + 1); 
      QFGInt.Number[0] := s; 
   End; 
   QFGInt.Sign := positive; 
 
   FGIntDestroy(temp1); 
   Base10StringToFGInt('0', zero); 
   Base10StringToFGInt('1', one); 
   If s1 = negative Then 
   Begin 
      If FGIntCompareAbs(MFGInt, zero) <> Eq Then 
      Begin 
         FGIntadd(QFGInt, one, temp1); 
         FGIntCopy(temp1, QFGInt); 
         FGIntDestroy(temp1); 
         FGIntsub(FGInt2, MFGInt, temp1); 
         FGIntCopy(temp1, MFGInt); 
      End; 
      If s2 = positive Then QFGInt.Sign := negative; 
   End 
   Else QFGInt.Sign := s2; 
   FGIntDestroy(one); 
   FGIntDestroy(zero); 
 
   FGInt1.Sign := s1; 
   FGInt2.Sign := s2; 
End; 
 
 
// Same as above but doesn 't compute MFGInt 
 
Procedure FGIntDiv(Var FGInt1, FGInt2, QFGInt : TFGInt); 
Var 
   one, zero, temp1, temp2, MFGInt : TFGInt; 
   s1, s2 : TSign; 
   i, j, s, t : longint; 
Begin 
   s1 := FGInt1.Sign; 
   s2 := FGInt2.Sign; 
   FGIntAbs(FGInt1); 
   FGIntAbs(FGInt2); 
   FGIntCopy(FGInt1, MFGInt); 
   FGIntCopy(FGInt2, temp1); 
 
   If FGIntCompareAbs(FGInt1, FGInt2) <> St Then 
   Begin 
      s := FGInt1.Number[0] - FGInt2.Number[0]; 
      setlength(QFGInt.Number, s + 2); 
      QFGInt.Number[0] := s + 1; 
      For t := 1 To s Do 
      Begin 
         FGIntShiftLeftBy31(temp1); 
         QFGInt.Number[t] := 0; 
      End; 
      j := s + 1; 
      QFGInt.Number[j] := 0; 
      While FGIntCompareAbs(MFGInt, FGInt2) <> St Do 
      Begin 
         While FGIntCompareAbs(MFGInt, temp1) <> St Do 
         Begin 
            If MFGInt.Number[0] > temp1.Number[0] Then 
               i := (2147483648 * MFGInt.Number[MFGInt.Number[0]] + MFGInt.Number[MFGInt.Number[0] - 1]) Div (temp1.Number[temp1.Number[0]] + 1) 
            Else i := MFGInt.Number[MFGInt.Number[0]] Div (temp1.Number[temp1.Number[0]] + 1); 
            If (i <> 0) Then 
            Begin 
               FGIntCopy(temp1, temp2); 
               FGIntMulByIntBis(temp2, i); 
               FGIntSubBis(MFGInt, temp2); 
               QFGInt.Number[j] := QFGInt.Number[j] + i; 
               If FGIntCompareAbs(MFGInt, temp2) <> St Then 
               Begin 
                  QFGInt.Number[j] := QFGInt.Number[j] + i; 
                  FGIntSubBis(MFGInt, temp2); 
               End; 
            End Else 
            Begin 
               QFGInt.Number[j] := QFGInt.Number[j] + 1; 
               FGIntSubBis(MFGInt, temp1); 
            End; 
         End; 
         If MFGInt.Number[0] <= temp1.Number[0] Then 
            If FGIntCompareAbs(temp1, FGInt2) <> Eq Then 
            Begin 
               FGIntShiftRightBy31(temp1); 
               j := j - 1; 
            End; 
      End; 
   End 
   Else Base10StringToFGInt('0', QFGInt); 
   s := QFGInt.Number[0]; 
   While (s > 1) And (QFGInt.Number[s] = 0) Do s := s - 1; 
   If s < QFGInt.Number[0] Then 
   Begin 
      setlength(QFGInt.Number, s + 1); 
      QFGInt.Number[0] := s; 
   End; 
   QFGInt.Sign := positive; 
 
   FGIntDestroy(temp1); 
   Base10StringToFGInt('0', zero); 
   Base10StringToFGInt('1', one); 
   If s1 = negative Then 
   Begin 
      If FGIntCompareAbs(MFGInt, zero) <> Eq Then 
      Begin 
         FGIntadd(QFGInt, one, temp1); 
         FGIntCopy(temp1, QFGInt); 
         FGIntDestroy(temp1); 
         FGIntsub(FGInt2, MFGInt, temp1); 
         FGIntCopy(temp1, MFGInt); 
      End; 
      If s2 = positive Then QFGInt.Sign := negative; 
   End 
   Else QFGInt.Sign := s2; 
   FGIntDestroy(one); 
   FGIntDestroy(zero); 
   FGIntDestroy(MFGInt); 
 
   FGInt1.Sign := s1; 
   FGInt2.Sign := s2; 
End; 
 
 
// Same as above but this computes MFGInt in stead of QFGInt 
// MFGInt = FGInt1 mod FGInt2 
 
Procedure FGIntMod(Var FGInt1, FGInt2, MFGInt : TFGInt); 
Var 
   one, zero, temp1, temp2 : TFGInt; 
   s1, s2 : TSign; 
   i : int64; 
   s, t : longint; 
Begin 
   s1 := FGInt1.Sign; 
   s2 := FGInt2.Sign; 
   FGIntAbs(FGInt1); 
   FGIntAbs(FGInt2); 
   FGIntCopy(FGInt1, MFGInt); 
   FGIntCopy(FGInt2, temp1); 
 
   If FGIntCompareAbs(FGInt1, FGInt2) <> St Then 
   Begin 
      s := FGInt1.Number[0] - FGInt2.Number[0]; 
      For t := 1 To s Do FGIntShiftLeftBy31(temp1); 
      While FGIntCompareAbs(MFGInt, FGInt2) <> St Do 
      Begin 
         While FGIntCompareAbs(MFGInt, temp1) <> St Do 
         Begin 
            If MFGInt.Number[0] > temp1.Number[0] Then 
               i := (2147483648 * MFGInt.Number[MFGInt.Number[0]] + MFGInt.Number[MFGInt.Number[0] - 1]) Div (temp1.Number[temp1.Number[0]] + 1) 
            Else i := MFGInt.Number[MFGInt.Number[0]] Div (temp1.Number[temp1.Number[0]] + 1); 
            If (i <> 0) Then 
            Begin 
               FGIntCopy(temp1, temp2); 
               FGIntMulByIntBis(temp2, i); 
               FGIntSubBis(MFGInt, temp2); 
               If FGIntCompareAbs(MFGInt, temp2) <> St Then FGIntSubBis(MFGInt, temp2); 
            End Else FGIntSubBis(MFGInt, temp1); 
//         If FGIntCompareAbs(MFGInt, temp1) <> St Then FGIntSubBis(MFGInt,temp1); 
         End; 
         If MFGInt.Number[0] <= temp1.Number[0] Then 
            If FGIntCompareAbs(temp1, FGInt2) <> Eq Then FGIntShiftRightBy31(temp1); 
      End; 
   End; 
 
   FGIntDestroy(temp1); 
   Base10StringToFGInt('0', zero); 
   Base10StringToFGInt('1', one); 
   If s1 = negative Then 
   Begin 
      If FGIntCompareAbs(MFGInt, zero) <> Eq Then 
      Begin 
         FGIntSub(FGInt2, MFGInt, temp1); 
         FGIntCopy(temp1, MFGInt); 
      End; 
   End; 
   FGIntDestroy(one); 
   FGIntDestroy(zero); 
 
   FGInt1.Sign := s1; 
   FGInt2.Sign := s2; 
End; 
 
 
// Square a FGInt modulo Modb, FGInt^2 mod Modb = FGIntSM 
 
Procedure FGIntSquareMod(Var FGInt, Modb, FGIntSM : TFGInt); 
Var 
   temp : TFGInt; 
Begin 
   FGIntSquare(FGInt, temp); 
   FGIntMod(temp, Modb, FGIntSM); 
   FGIntDestroy(temp); 
End; 
 
 
// Add 2 FGInts modulo base, (FGInt1 + FGInt2) mod base = FGIntres 
 
Procedure FGIntAddMod(Var FGInt1, FGInt2, base, FGIntres : TFGInt); 
Var 
   temp : TFGInt; 
Begin 
   FGIntadd(FGInt1, FGInt2, temp); 
   FGIntMod(temp, base, FGIntres); 
   FGIntDestroy(temp); 
End; 
 
 
// Multiply 2 FGInts modulo base, (FGInt1 * FGInt2) mod base = FGIntres 
 
Procedure FGIntMulMod(Var FGInt1, FGInt2, base, FGIntres : TFGInt); 
Var 
   temp : TFGInt; 
Begin 
   FGIntMul(FGInt1, FGInt2, temp); 
   FGIntMod(temp, base, FGIntres); 
   FGIntDestroy(temp); 
End; 
 
 
// Exponentiate 2 FGInts modulo base, (FGInt1 ^ FGInt2) mod modb = res 
 
Procedure FGIntModExp(Var FGInt, exp, modb, res : TFGInt); 
Var 
   temp2, temp3 : TFGInt; 
   i : longint; 
   S : String; 
Begin 
   If (Modb.Number[1] Mod 2) = 1 Then 
   Begin 
      FGIntMontgomeryModExp(FGInt, exp, modb, res); 
      exit; 
   End; 
   FGIntToBase2String(exp, S); 
   Base10StringToFGInt('1', res); 
   FGIntcopy(FGInt, temp2); 
 
   For i := length(S) Downto 1 Do 
   Begin 
      If S[i] = '1' Then 
      Begin 
         FGIntmulMod(res, temp2, modb, temp3); 
         FGIntCopy(temp3, res); 
      End; 
      FGIntSquareMod(temp2, Modb, temp3); 
      FGIntCopy(temp3, temp2); 
   End; 
   FGIntDestroy(temp2); 
End; 
 
 
// Procedures for Montgomery Exponentiation 
 
Procedure FGIntModBis(Const FGInt : TFGInt; Var FGIntOut : TFGInt; b : longint; head : int64); 
Var 
   i : longint; 
Begin 
   If b <= FGInt.Number[0] Then 
   Begin 
      FGIntOut.Number := Copy(FGInt.Number, 0, b + 1); 
      FGIntOut.Number[b] := FGIntOut.Number[b] And head; 
      i := b; 
      While (FGIntOut.Number[i] = 0) And (i > 1) Do i := i - 1; 
      If i < b Then SetLength(FGIntOut.Number, i + 1); 
      FGIntOut.Number[0] := i; 
      FGIntOut.Sign := positive; 
   End Else FGIntCopy(FGInt, FGIntOut); 
End; 
 
 
Procedure FGIntMulModBis(Const FGInt1, FGInt2 : TFGInt; Var Prod : TFGInt; b : longint; head : int64); 
Var 
   i, j, size, size1, size2, t : longint; 
   rest, Trest : int64; 
Begin 
   size1 := FGInt1.Number[0]; 
   size2 := FGInt2.Number[0]; 
   size := min(b, size1 + size2); 
   SetLength(Prod.Number, size + 1); 
   For i := 1 To size Do Prod.Number[i] := 0; 
 
   For i := 1 To size2 Do 
   Begin 
      rest := 0; 
      t := min(size1, b - i + 1); 
      For j := 1 To t Do 
      Begin 
         Trest := Prod.Number[j + i - 1] + FGInt1.Number[j] * FGInt2.Number[i] + rest; 
         Prod.Number[j + i - 1] := Trest And 2147483647; 
         rest := Trest Shr 31; 
      End; 
      If (i + size1) <= b Then Prod.Number[i + size1] := rest; 
   End; 
 
   Prod.Number[0] := size; 
   If size = b Then Prod.Number[b] := Prod.Number[b] And head; 
   While (Prod.Number[size] = 0) And (size > 1) Do size := size - 1; 
   If size < Prod.Number[0] Then 
   Begin 
      SetLength(Prod.Number, size + 1); 
      Prod.Number[0] := size; 
   End; 
   If FGInt1.Sign = FGInt2.Sign Then Prod.Sign := Positive Else prod.Sign := negative; 
End; 
 
 
Procedure FGIntMontgomeryMod(Const GInt, base, baseInv : TFGInt; Var MGInt : TFGInt; b : longint; head : int64); 
Var 
   m, temp, temp1 : TFGInt; 
   r : int64; 
Begin 
   FGIntModBis(GInt, temp, b, head); 
   FGIntMulModBis(temp, baseInv, m, b, head); 
   FGIntMul(m, base, temp1); 
   FGIntDestroy(temp); 
   FGIntAdd(temp1, GInt, temp); 
   FGIntDestroy(temp1); 
   MGInt.Number := copy(temp.Number, b - 1, temp.Number[0] - b + 2); 
   MGInt.Sign := positive; 
   MGInt.Number[0] := temp.Number[0] - b + 1; 
   FGIntDestroy(temp); 
   If (head Shr 30) = 0 Then FGIntDivByIntBis(MGInt, head + 1, r) 
   Else FGIntShiftRightBy31(MGInt); 
   If FGIntCompareAbs(MGInt, base) <> St Then FGIntSubBis(MGInt, base); 
   FGIntDestroy(temp); 
   FGIntDestroy(m); 
End; 
 
 
Procedure FGIntMontgomeryModExp(Var FGInt, exp, modb, res : TFGInt); 
Var 
   temp2, temp3, baseInv, r : TFGInt; 
   i, j, t, b : longint; 
   S : String; 
   head : int64; 
Begin 
   FGIntToBase2String(exp, S); 
   t := modb.Number[0]; 
   b := t; 
 
   If (modb.Number[t] Shr 30) = 1 Then t := t + 1; 
   setlength(r.Number, t + 1); 
   r.Number[0] := t; 
   r.Sign := positive; 
   For i := 1 To t Do r.Number[i] := 0; 
   If t = modb.Number[0] Then 
   Begin 
      head := 2147483647; 
      For j := 29 Downto 0 Do 
      Begin 
         head := head Shr 1; 
         If (modb.Number[t] Shr j) = 1 Then 
         Begin 
            r.Number[t] := 1 Shl (j + 1); 
            break; 
         End; 
      End; 
   End 
   Else 
   Begin 
      r.Number[t] := 1; 
      head := 2147483647; 
   End; 
 
   FGIntModInv(modb, r, temp2); 
   If temp2.Sign = negative Then FGIntCopy(temp2, BaseInv) 
   Else 
   Begin 
      FGIntCopy(r, BaseInv); 
      FGIntSubBis(BaseInv, temp2); 
   End; 
//   FGIntBezoutBachet(r, modb, temp2, BaseInv); 
   FGIntAbs(BaseInv); 
   FGIntDestroy(temp2); 
   FGIntMod(r, modb, res); 
   FGIntMulMod(FGInt, res, modb, temp2); 
   FGIntDestroy(r); 
 
   For i := length(S) Downto 1 Do 
   Begin 
      If S[i] = '1' Then 
      Begin 
         FGIntmul(res, temp2, temp3); 
         FGIntDestroy(res); 
         FGIntMontgomeryMod(temp3, modb, baseinv, res, b, head); 
         FGIntDestroy(temp3); 
      End; 
      FGIntSquare(temp2, temp3); 
      FGIntDestroy(temp2); 
      FGIntMontgomeryMod(temp3, modb, baseinv, temp2, b, head); 
      FGIntDestroy(temp3); 
   End; 
   FGIntDestroy(temp2); 
   FGIntMontgomeryMod(res, modb, baseinv, temp3, b, head); 
   FGIntCopy(temp3, res); 
   FGIntDestroy(temp3); 
   FGIntDestroy(baseinv); 
End; 
 
 
// Compute the Greatest Common Divisor of 2 FGInts 
 
Procedure FGIntGCD(Const FGInt1, FGInt2 : TFGInt; Var GCD : TFGInt); 
Var 
   k : TCompare; 
   zero, temp1, temp2, temp3 : TFGInt; 
Begin 
   k := FGIntCompareAbs(FGInt1, FGInt2); 
   If (k = Eq) Then FGIntCopy(FGInt1, GCD) Else 
      If (k = St) Then FGIntGCD(FGInt2, FGInt1, GCD) Else 
      Begin 
         Base10StringToFGInt('0', zero); 
         FGIntCopy(FGInt1, temp1); 
         FGIntCopy(FGInt2, temp2); 
         While (temp2.Number[0] <> 1) Or (temp2.Number[1] <> 0) Do 
         Begin 
            FGIntMod(temp1, temp2, temp3); 
            FGIntCopy(temp2, temp1); 
            FGIntCopy(temp3, temp2); 
            FGIntDestroy(temp3); 
         End; 
         FGIntCopy(temp1, GCD); 
         FGIntDestroy(temp2); 
         FGIntDestroy(zero); 
      End; 
End; 
 
 
// Compute the Least Common Multiple of 2 FGInts 
 
Procedure FGIntLCM(Const FGInt1, FGInt2 : TFGInt; Var LCM : TFGInt); 
Var 
   temp1, temp2 : TFGInt; 
Begin 
   FGIntGCD(FGInt1, FGInt2, temp1); 
   FGIntmul(FGInt1, FGInt2, temp2); 
   FGIntdiv(temp2, temp1, LCM); 
   FGIntDestroy(temp1); 
   FGIntDestroy(temp2); 
End; 
 
 
// Trialdivision of a FGInt upto 9999 and stopping when a divisor is found, returning ok=false 
 
Procedure FGIntTrialDiv9999(Const FGInt : TFGInt; Var ok : boolean); 
Var 
   j : int64; 
   i : integer; 
Begin 
   If ((FGInt.Number[1] Mod 2) = 0) Then ok := false 
   Else 
   Begin 
      i := 0; 
      ok := true; 
      While ok And (i < 1228) Do 
      Begin 
         i := i + 1; 
         FGIntmodbyint(FGInt, primes[i], j); 
         If j = 0 Then ok := false; 
      End; 
   End; 
End; 
 
 
// A prng 
 
Procedure FGIntRandom1(Var Seed, RandomFGInt : TFGInt); 
Var 
   temp, base : TFGInt; 
Begin 
   Base10StringToFGInt('281474976710656', base); 
   Base10StringToFGInt('44485709377909', temp); 
   FGIntMulMod(seed, temp, base, RandomFGInt); 
   FGIntDestroy(temp); 
   FGIntDestroy(base); 
End; 
 
 
// Perform a Rabin Miller Primality Test nrtest times on FGIntp, returns ok=true when FGIntp passes the test 
 
Procedure FGIntRabinMiller(Var FGIntp : TFGInt; nrtest : integer; Var ok : boolean); 
Var 
   j, b, i : int64; 
   m, z, temp1, temp2, temp3, zero, one, two, pmin1 : TFGInt; 
   ok1, ok2 : boolean; 
Begin 
   randomize; 
   j := 0; 
   Base10StringToFGInt('0', zero); 
   Base10StringToFGInt('1', one); 
   Base10StringToFGInt('2', two); 
   FGIntsub(FGIntp, one, temp1); 
   FGIntsub(FGIntp, one, pmin1); 
 
   b := 0; 
   While (temp1.Number[1] Mod 2) = 0 Do 
   Begin 
      b := b + 1; 
      FGIntShiftRight(temp1); 
   End; 
   m := temp1; 
 
   i := 0; 
   ok := true; 
   Randomize; 
   While (i < nrtest) And ok Do 
   Begin 
      i := i + 1; 
      Base10StringToFGInt(inttostr(Primes[Random(1227) + 1]), temp2); 
      FGIntMontGomeryModExp(temp2, m, FGIntp, z); 
      FGIntDestroy(temp2); 
      ok1 := (FGIntCompareAbs(z, one) = Eq); 
      ok2 := (FGIntCompareAbs(z, pmin1) = Eq); 
      If Not (ok1 Or ok2) Then 
      Begin 
 
         While (ok And (j < b)) Do 
         Begin 
            If (j > 0) And ok1 Then ok := false 
            Else 
            Begin 
               j := j + 1; 
               If (j < b) And (Not ok2) Then 
               Begin 
                  FGIntSquaremod(z, FGIntp, temp3); 
                  FGIntCopy(temp3, z); 
                  ok1 := (FGIntCompareAbs(z, one) = Eq); 
                  ok2 := (FGIntCompareAbs(z, pmin1) = Eq); 
                  If ok2 Then j := b; 
               End 
               Else If (Not ok2) And (j >= b) Then ok := false; 
            End; 
         End; 
 
      End 
   End; 
 
   FGIntDestroy(zero); 
   FGIntDestroy(one); 
   FGIntDestroy(two); 
   FGIntDestroy(m); 
   FGIntDestroy(z); 
   FGIntDestroy(pmin1); 
End; 
 
 
// Compute the coefficients from the Bezout Bachet theorem, FGInt1 * a + FGInt2 * b = GCD(FGInt1, FGInt2) 
 
Procedure FGIntBezoutBachet(Var FGInt1, FGInt2, a, b : TFGInt); 
Var 
   zero, r1, r2, r3, ta, gcd, temp, temp1, temp2 : TFGInt; 
Begin 
   If FGIntCompareAbs(FGInt1, FGInt2) <> St Then 
   Begin 
      FGIntcopy(FGInt1, r1); 
      FGIntcopy(FGInt2, r2); 
      Base10StringToFGInt('0', zero); 
      Base10StringToFGInt('1', a); 
      Base10StringToFGInt('0', ta); 
 
      Repeat 
         FGIntdivmod(r1, r2, temp, r3); 
         FGIntDestroy(r1); 
         r1 := r2; 
         r2 := r3; 
 
         FGIntmul(ta, temp, temp1); 
         FGIntsub(a, temp1, temp2); 
         FGIntCopy(ta, a); 
         FGIntCopy(temp2, ta); 
         FGIntDestroy(temp1); 
 
         FGIntDestroy(temp); 
      Until FGIntCompareAbs(r3, zero) = Eq; 
 
      FGIntGCD(FGInt1, FGInt2, gcd); 
      FGIntmul(a, FGInt1, temp1); 
      FGIntsub(gcd, temp1, temp2); 
      FGIntDestroy(temp1); 
      FGIntdiv(temp2, FGInt2, b); 
      FGIntDestroy(temp2); 
 
      FGIntDestroy(ta); 
      FGIntDestroy(r1); 
      FGIntDestroy(r2); 
      FGIntDestroy(gcd); 
   End 
   Else FGIntBezoutBachet(FGInt2, FGInt1, b, a); 
End; 
 
 
// Find the (multiplicative) Modular inverse of a FGInt in a finite ring 
// of additive order base 
 
Procedure FGIntModInv(Const FGInt1, base : TFGInt; Var Inverse : TFGInt); 
Var 
   zero, one, r1, r2, r3, tb, gcd, temp, temp1, temp2 : TFGInt; 
Begin 
   Base10StringToFGInt('1', one); 
   FGIntGCD(FGInt1, base, gcd); 
   If FGIntCompareAbs(one, gcd) = Eq Then 
   Begin 
      FGIntcopy(base, r1); 
      FGIntcopy(FGInt1, r2); 
      Base10StringToFGInt('0', zero); 
      Base10StringToFGInt('0', inverse); 
      Base10StringToFGInt('1', tb); 
 
      Repeat 
         FGIntDestroy(r3); 
         FGIntdivmod(r1, r2, temp, r3); 
         FGIntCopy(r2, r1); 
         FGIntCopy(r3, r2); 
 
         FGIntmul(tb, temp, temp1); 
         FGIntsub(inverse, temp1, temp2); 
         FGIntDestroy(inverse); 
         FGIntDestroy(temp1); 
         FGIntCopy(tb, inverse); 
         FGIntCopy(temp2, tb); 
 
         FGIntDestroy(temp); 
      Until FGIntCompareAbs(r3, zero) = Eq; 
 
      If inverse.Sign = negative Then 
      Begin 
         FGIntadd(base, inverse, temp); 
         FGIntCopy(temp, inverse); 
      End; 
 
      FGIntDestroy(tb); 
      FGIntDestroy(r1); 
      FGIntDestroy(r2); 
   End; 
   FGIntDestroy(gcd); 
   FGIntDestroy(one); 
End; 
 
 
// Perform a (combined) primality test on FGIntp consisting of a trialdivision upto 8192, 
// if the FGInt passes perform nrRMtests Rabin Miller primality tests, returns ok when a 
// FGInt is probably prime 
 
Procedure FGIntPrimetest(Var FGIntp : TFGInt; nrRMtests : integer; Var ok : boolean); 
Begin 
   FGIntTrialdiv9999(FGIntp, ok); 
   If ok Then FGIntRabinMiller(FGIntp, nrRMtests, ok); 
End; 
 
 
// Computes the Legendre symbol for a any number and 
// p a prime, returns 0 if p divides a, 1 if a is a 
// quadratic residu mod p, -1 if a is a quadratic 
// nonresidu mod p 
 
Procedure FGIntLegendreSymbol(Var a, p : TFGInt; Var L : integer); 
Var 
   temp1, temp2, temp3, temp4, temp5, zero, one : TFGInt; 
   i : int64; 
   ok1, ok2 : boolean; 
Begin 
   Base10StringToFGInt('0', zero); 
   Base10StringToFGInt('1', one); 
   FGIntMod(a, p, temp1); 
   If FGIntCompareAbs(zero, temp1) = Eq Then 
   Begin 
      FGIntDestroy(temp1); 
      L := 0; 
   End 
   Else 
   Begin 
      FGIntDestroy(temp1); 
      FGIntCopy(p, temp1); 
      FGIntCopy(a, temp2); 
      L := 1; 
      While FGIntCompareAbs(temp2, one) <> Eq Do 
      Begin 
         If (temp2.Number[1] Mod 2) = 0 Then 
         Begin 
            FGIntSquare(temp1, temp3); 
            FGIntSub(temp3, one, temp4); 
            FGIntDestroy(temp3); 
            FGIntDivByInt(temp4, temp3, 8, i); 
            If (temp3.Number[1] Mod 2) = 0 Then ok1 := false Else ok1 := true; 
            FGIntDestroy(temp3); 
            FGIntDestroy(temp4); 
            If ok1 = true Then L := L * (-1); 
            FGIntDivByIntBis(temp2, 2, i); 
         End 
         Else 
         Begin 
            FGIntSub(temp1, one, temp3); 
            FGIntSub(temp2, one, temp4); 
            FGIntMul(temp3, temp4, temp5); 
            FGIntDestroy(temp3); 
            FGIntDestroy(temp4); 
            FGIntDivByInt(temp5, temp3, 4, i); 
            If (temp3.Number[1] Mod 2) = 0 Then ok2 := false Else ok2 := true; 
            FGIntDestroy(temp5); 
            FGIntDestroy(temp3); 
            If ok2 = true Then L := L * (-1); 
            FGIntMod(temp1, temp2, temp3); 
            FGIntCopy(temp2, temp1); 
            FGIntCopy(temp3, temp2); 
         End; 
      End; 
      FGIntDestroy(temp1); 
      FGIntDestroy(temp2); 
   End; 
   FGIntDestroy(zero); 
   FGIntDestroy(one); 
End; 
 
 
// Compute a square root modulo a prime number 
// SquareRoot^2 mod Prime = Square 
 
Procedure FGIntSquareRootModP(Square, Prime : TFGInt; Var SquareRoot : TFGInt); 
Var 
   one, n, b, s, r, temp, temp1, temp2, temp3 : TFGInt; 
   a, L, i, j : longint; 
Begin 
   Base2StringToFGInt('1', one); 
   Base2StringToFGInt('10', n); 
   a := 0; 
   FGIntLegendreSymbol(n, Prime, L); 
   While L <> -1 Do 
   Begin 
      FGIntAddBis(n, one); 
      FGIntLegendreSymbol(n, Prime, L); 
   End; 
   FGIntCopy(Prime, s); 
   s.Number[1] := s.Number[1] - 1; 
   While (s.Number[1] Mod 2) = 0 Do 
   Begin 
      FGIntShiftRight(s); 
      a := a + 1; 
   End; 
   FGIntMontgomeryModExp(n, s, Prime, b); 
   FGIntAdd(s, one, temp); 
   FGIntShiftRight(temp); 
   FGIntMontgomeryModExp(Square, temp, Prime, r); 
   FGIntDestroy(temp); 
   FGIntModInv(Square, Prime, temp1); 
 
   For i := 0 To (a - 2) Do 
   Begin 
      FGIntSquareMod(r, Prime, temp2); 
      FGIntMulMod(temp1, temp2, Prime, temp); 
      FGIntDestroy(temp2); 
      For j := 1 To (a - i - 2) Do 
      Begin 
         FGIntSquareMod(temp, Prime, temp2); 
         FGIntDestroy(temp); 
         FGIntCopy(temp2, temp); 
         FGIntDestroy(temp2); 
      End; 
      If FGIntCompareAbs(temp, one) <> Eq Then 
      Begin 
         FGIntMulMod(r, b, Prime, temp3); 
         FGIntDestroy(r); 
         FGIntCopy(temp3, r); 
         FGIntDestroy(temp3); 
      End; 
      FGIntDestroy(temp); 
      FGIntDestroy(temp2); 
      If i = (a - 2) Then break; 
      FGIntSquareMod(b, Prime, temp3); 
      FGIntDestroy(b); 
      FGIntCopy(temp3, b); 
      FGIntDestroy(temp3); 
   End; 
 
   FGIntCopy(r, SquareRoot); 
   FGIntDestroy(r); 
   FGIntDestroy(s); 
   FGIntDestroy(b); 
   FGIntDestroy(temp1); 
   FGIntDestroy(one); 
   FGIntDestroy(n); 
End; 
 
 
End.