📄 lbbigint.pas
字号:
(* ***** BEGIN LICENSE BLOCK *****
* Version: MPL 1.1
*
* The contents of this file are subject to the Mozilla Public License Version
* 1.1 (the "License"); you may not use this file except in compliance with
* the License. You may obtain a copy of the License at
* http://www.mozilla.org/MPL/
*
* Software distributed under the License is distributed on an "AS IS" basis,
* WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
* for the specific language governing rights and limitations under the
* License.
*
* The Original Code is TurboPower LockBox
*
* The Initial Developer of the Original Code is
* TurboPower Software
*
* Portions created by the Initial Developer are Copyright (C) 1997-2002
* the Initial Developer. All Rights Reserved.
*
* Contributor(s):
*
* ***** END LICENSE BLOCK ***** *)
{*********************************************************}
{* LBBIGINT.PAS 2.07 *}
{* Copyright (c) 2002 TurboPower Software Co *}
{* All rights reserved. *}
{*********************************************************}
{$I LockBox.inc}
unit LbBigInt;
{-bigInteger math routines}
interface
uses
{$IFDEF MSWINDOWS}
Windows,
{$ENDIF}
{$IFDEF UsingCLX}
Types,
{$ENDIF}
Sysutils,
LbRandom;
const
cLESS_THAN = shortInt(-1);
cEQUAL_TO = shortInt(0);
cGREATER_THAN = shortInt(1);
cPOSITIVE = True;
cNEGATIVE = False;
{ LbInteger record }
type
LbIntBuf = packed record
dwLen : integer; {!!03}
pBuf : pByte;
end;
LbInteger = packed record
bSign : Boolean;
dwUsed : integer; {!!03}
IntBuf : LbIntBuf;
end;
{ TLbBigInt }
type
TLbBigInt = class
protected {private}
FI : LbInteger;
procedure setSign(value : Boolean);
function getSign : Boolean;
function GetSize : integer; {!!03}
function GetIntStr : string;
function GetIntBuf : pByte;
public
constructor Create(ALen : Integer);
destructor Destroy; override;
procedure Add(I2 : TLbBigInt);
procedure Subtract(I2 : TLbBigInt);
procedure Multiply(I2 : TLbBigInt);
procedure Divide(I2 : TLbBigInt);
procedure Modulus(I2 : TLbBigInt);
function ModInv(Modulus : TLbBigInt) : Boolean;
procedure PowerAndMod(Exponent : TLbBigInt; modulus : TLbBigInt);
procedure AddByte(b : byte);
procedure SubtractByte(b : byte);
procedure MultiplyByte(b : byte);
procedure DivideByte(b : byte);
procedure ModByte(b : byte);
procedure Clear;
procedure Trim;
function Compare(I2 : TLbBigInt) : ShortInt;
function IsZero : Boolean;
function IsOne : Boolean;
function IsOdd : Boolean;
function IsEven : Boolean;
function IsComposite(Iterations : Cardinal) : Boolean;
function Abs(I2 : TLbBigInt) : ShortInt;
procedure ReverseBits;
procedure ReverseBytes;
function GetBit(bit : Integer) : Boolean;
procedure Shr_(_shr : Integer);
procedure Shl_(_shl : Integer);
procedure OR_(I2 : TLbBigInt);
procedure XOR_(I2 : TLbBigInt);
procedure RandomBytes(Count : Cardinal);
procedure RandomPrime(Iterations : Byte);
procedure RandomSimplePrime;
procedure Copy(I2 : TLbBigInt);
procedure CopyLen(I2 : TLbBigInt; Len : Integer);
procedure CopyByte(b : byte);
procedure CopyWord(w : word);
procedure CopyDWord(d : dword);
procedure CopyBuffer(const Buf; BufLen : Integer);
procedure Append(I : TLbBigInt);
procedure AppendByte(b : byte);
procedure AppendWord(w : word);
procedure AppendDWord(d : dword);
procedure AppendBuffer(const Buf; BufLen : Integer);
procedure Prepend(I : TLbBigInt);
procedure PrependByte(b : byte);
procedure PrependWord(w : word);
procedure PrependDWord(d : dword);
procedure PrependBuffer(const Buf; BufLen : Integer);
function ToBuffer(var Buf; BufLen : Integer) : integer;
function GetByteValue( place : integer ) : Byte;
property Sign : Boolean
read getSign write setSign;
property Int : LbInteger
read FI;
property IntBuf : pByte
read GetIntBuf;
property IntStr : string
read GetIntStr;
property Size : integer {!!03}
read GetSize;
end;
implementation
uses
{$IFDEF Debugging} Dialogs, {$ENDIF}
LbUtils, LbConst;
const { misc local constants }
cBYTE_POSSIBLE_VALUES = 256;
cDEFAULT_PRECISION = 64;
cUSE_DEFAULT_PRECISION = 0;
cDEFAULT_SIGN = cPOSITIVE;
cDEFAULT_USED = 0;
cAPPEND_ARRAY = 0;
cPREPEND_ARRAY = 1;
cDEFAULT_MAX_PRECISION = 256;
const { simple prime table }
cTotalSimplePrimes = (258 * 8);
cTotalSimpleBytePrimes = 53; { %80 elimination }
cTotalSimple2KPrimes = 303;
type
pBiByteArray = ^TBiByteArray;
pBiWordArray = ^TBiWordArray;
// TBiByteArray = array[0..65535] of Byte;
TBiByteArray = array[0..pred(maxint)] of Byte;
TBiWordArray = array[0..pred(maxint div 2 )] of word;
const
cMaxBigIntSize = SizeOf( TByteArray );
const
{ source :
http://www.geocities.com/ResearchTriangle/Thinktank/2434/prime/primenumbers.html }
SimplePrimes : array[ 0..pred(cTotalSimplePrimes)] of DWord = ( {!!.01}
2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , // 1
23 , 29 , 31 , 37 , 41 , 43 , 47 , 53 , // 2
59 , 61 , 67 , 71 , 73 , 79 , 83 , 89 , // 3
97 , 101 , 103 , 107 , 109 , 113 , 127 , 131 , // 4
137 , 139 , 149 , 151 , 157 , 163 , 167 , 173 , // 5
179 , 181 , 191 , 193 , 197 , 199 , 211 , 223 , // 6
227 , 229 , 233 , 239 , 241 , 251 , 257 , 263 , // 7 < 256 = 53
269 , 271 , 277 , 281 , 283 , 293 , 307 , 311 , // 8
313 , 317 , 331 , 337 , 347 , 349 , 353 , 359 , // 9
367 , 373 , 379 , 383 , 389 , 397 , 401 , 409 , // 10
419 , 421 , 431 , 433 , 439 , 443 , 449 , 457 , // 11
461 , 463 , 467 , 479 , 487 , 491 , 499 , 503 , // 12
509 , 521 , 523 , 541 , 547 , 557 , 563 , 569 , // 13
571 , 577 , 587 , 593 , 599 , 601 , 607 , 613 , // 14
617 , 619 , 631 , 641 , 643 , 647 , 653 , 659 , // 15
661 , 673 , 677 , 683 , 691 , 701 , 709 , 719 , // 16
727 , 733 , 739 , 743 , 751 , 757 , 761 , 769 , // 17
773 , 787 , 797 , 809 , 811 , 821 , 823 , 827 , // 18
829 , 839 , 853 , 857 , 859 , 863 , 877 , 881 , // 19
883 , 887 , 907 , 911 , 919 , 929 , 937 , 941 , // 20
947 , 953 , 967 , 971 , 977 , 983 , 991 , 997 , // 21
1009 , 1013 , 1019 , 1021 , 1031 , 1033 , 1039 , 1049 , // 22
1051 , 1061 , 1063 , 1069 , 1087 , 1091 , 1093 , 1097 , // 23
1103 , 1109 , 1117 , 1123 , 1129 , 1151 , 1153 , 1163 , // 24
1171 , 1181 , 1187 , 1193 , 1201 , 1213 , 1217 , 1223 , // 25
1229 , 1231 , 1237 , 1249 , 1259 , 1277 , 1279 , 1283 , // 26
1289 , 1291 , 1297 , 1301 , 1303 , 1307 , 1319 , 1321 , // 27
1327 , 1361 , 1367 , 1373 , 1381 , 1399 , 1409 , 1423 , // 28
1427 , 1429 , 1433 , 1439 , 1447 , 1451 , 1453 , 1459 , // 29
1471 , 1481 , 1483 , 1487 , 1489 , 1493 , 1499 , 1511 , // 30
1523 , 1531 , 1543 , 1549 , 1553 , 1559 , 1567 , 1571 , // 31
1579 , 1583 , 1597 , 1601 , 1607 , 1609 , 1613 , 1619 , // 32
1621 , 1627 , 1637 , 1657 , 1663 , 1667 , 1669 , 1693 , // 33
1697 , 1699 , 1709 , 1721 , 1723 , 1733 , 1741 , 1747 , // 34
1753 , 1759 , 1777 , 1783 , 1787 , 1789 , 1801 , 1811 , // 35
1823 , 1831 , 1847 , 1861 , 1867 , 1871 , 1873 , 1877 , // 36
1879 , 1889 , 1901 , 1907 , 1913 , 1931 , 1933 , 1949 , // 37
1951 , 1973 , 1979 , 1987 , 1993 , 1997 , 1999 , 2003 , // 38 < 2000 = 303
2011 , 2017 , 2027 , 2029 , 2039 , 2053 , 2063 , 2069 , // 39
2081 , 2083 , 2087 , 2089 , 2099 , 2111 , 2113 , 2129 , // 40
2131 , 2137 , 2141 , 2143 , 2153 , 2161 , 2179 , 2203 , // 41
2207 , 2213 , 2221 , 2237 , 2239 , 2243 , 2251 , 2267 , // 42
2269 , 2273 , 2281 , 2287 , 2293 , 2297 , 2309 , 2311 , // 43
2333 , 2339 , 2341 , 2347 , 2351 , 2357 , 2371 , 2377 , // 44
2381 , 2383 , 2389 , 2393 , 2399 , 2411 , 2417 , 2423 , // 45
2437 , 2441 , 2447 , 2459 , 2467 , 2473 , 2477 , 2503 , // 46
2521 , 2531 , 2539 , 2543 , 2549 , 2551 , 2557 , 2579 , // 47
2591 , 2593 , 2609 , 2617 , 2621 , 2633 , 2647 , 2657 , // 48
2659 , 2663 , 2671 , 2677 , 2683 , 2687 , 2689 , 2693 , // 49
2699 , 2707 , 2711 , 2713 , 2719 , 2729 , 2731 , 2741 , // 50
2749 , 2753 , 2767 , 2777 , 2789 , 2791 , 2797 , 2801 , // 51
2803 , 2819 , 2833 , 2837 , 2843 , 2851 , 2857 , 2861 , // 52
2879 , 2887 , 2897 , 2903 , 2909 , 2917 , 2927 , 2939 , // 53
2953 , 2957 , 2963 , 2969 , 2971 , 2999 , 3001 , 3011 , // 54
3019 , 3023 , 3037 , 3041 , 3049 , 3061 , 3067 , 3079 , // 55
3083 , 3089 , 3109 , 3119 , 3121 , 3137 , 3163 , 3167 , // 56
3169 , 3181 , 3187 , 3191 , 3203 , 3209 , 3217 , 3221 , // 57
3229 , 3251 , 3253 , 3257 , 3259 , 3271 , 3299 , 3301 , // 58
3307 , 3313 , 3319 , 3323 , 3329 , 3331 , 3343 , 3347 , // 59
3359 , 3361 , 3371 , 3373 , 3389 , 3391 , 3407 , 3413 , // 60
3433 , 3449 , 3457 , 3461 , 3463 , 3467 , 3469 , 3491 , // 61
3499 , 3511 , 3517 , 3527 , 3529 , 3533 , 3539 , 3541 , // 62
3547 , 3557 , 3559 , 3571 , 3581 , 3583 , 3593 , 3607 , // 63
3613 , 3617 , 3623 , 3631 , 3637 , 3643 , 3659 , 3671 , // 64
3673 , 3677 , 3691 , 3697 , 3701 , 3709 , 3719 , 3727 , // 65
3733 , 3739 , 3761 , 3767 , 3769 , 3779 , 3793 , 3797 , // 66
3803 , 3821 , 3823 , 3833 , 3847 , 3851 , 3853 , 3863 , // 67
3877 , 3881 , 3889 , 3907 , 3911 , 3917 , 3919 , 3923 , // 68
3929 , 3931 , 3943 , 3947 , 3967 , 3989 , 4001 , 4003 , // 69
4007 , 4013 , 4019 , 4021 , 4027 , 4049 , 4051 , 4057 , // 70
4073 , 4079 , 4091 , 4093 , 4099 , 4111 , 4127 , 4129 , // 71
4133 , 4139 , 4153 , 4157 , 4159 , 4177 , 4201 , 4211 , // 72
4217 , 4219 , 4229 , 4231 , 4241 , 4243 , 4253 , 4259 , // 73
4261 , 4271 , 4273 , 4283 , 4289 , 4297 , 4327 , 4337 , // 74
4339 , 4349 , 4357 , 4363 , 4373 , 4391 , 4397 , 4409 , // 75
4421 , 4423 , 4441 , 4447 , 4451 , 4457 , 4463 , 4481 , // 76
4483 , 4493 , 4507 , 4513 , 4517 , 4519 , 4523 , 4547 , // 77
4549 , 4561 , 4567 , 4583 , 4591 , 4597 , 4603 , 4621 , // 78
4637 , 4639 , 4643 , 4649 , 4651 , 4657 , 4663 , 4673 , // 79
4679 , 4691 , 4703 , 4721 , 4723 , 4729 , 4733 , 4751 , // 80
4759 , 4783 , 4787 , 4789 , 4793 , 4799 , 4801 , 4813 , // 81
4817 , 4831 , 4861 , 4871 , 4877 , 4889 , 4903 , 4909 , // 82
4919 , 4931 , 4933 , 4937 , 4943 , 4951 , 4957 , 4967 , // 83
4969 , 4973 , 4987 , 4993 , 4999 , 5003 , 5009 , 5011 , // 84
5021 , 5023 , 5039 , 5051 , 5059 , 5077 , 5081 , 5087 , // 85
5099 , 5101 , 5107 , 5113 , 5119 , 5147 , 5153 , 5167 , // 86
5171 , 5179 , 5189 , 5197 , 5209 , 5227 , 5231 , 5233 , // 87
5237 , 5261 , 5273 , 5279 , 5281 , 5297 , 5303 , 5309 , // 88
5323 , 5333 , 5347 , 5351 , 5381 , 5387 , 5393 , 5399 , // 89
5407 , 5413 , 5417 , 5419 , 5431 , 5437 , 5441 , 5443 , // 90
5449 , 5471 , 5477 , 5479 , 5483 , 5501 , 5503 , 5507 , // 91
5519 , 5521 , 5527 , 5531 , 5557 , 5563 , 5569 , 5573 , // 92
5581 , 5591 , 5623 , 5639 , 5641 , 5647 , 5651 , 5653 , // 93
5657 , 5659 , 5669 , 5683 , 5689 , 5693 , 5701 , 5711 , // 94
5717 , 5737 , 5741 , 5743 , 5749 , 5779 , 5783 , 5791 , // 95
5801 , 5807 , 5813 , 5821 , 5827 , 5839 , 5843 , 5849 , // 96
5851 , 5857 , 5861 , 5867 , 5869 , 5879 , 5881 , 5897 , // 97
5903 , 5923 , 5927 , 5939 , 5953 , 5981 , 5987 , 6007 , // 98
6011 , 6029 , 6037 , 6043 , 6047 , 6053 , 6067 , 6073 , // 99
6079 , 6089 , 6091 , 6101 , 6113 , 6121 , 6131 , 6133 , // 100
6143 , 6151 , 6163 , 6173 , 6197 , 6199 , 6203 , 6211 , // 101
6217 , 6221 , 6229 , 6247 , 6257 , 6263 , 6269 , 6271 , // 102
6277 , 6287 , 6299 , 6301 , 6311 , 6317 , 6323 , 6329 , // 103
6337 , 6343 , 6353 , 6359 , 6361 , 6367 , 6373 , 6379 , // 104
6389 , 6397 , 6421 , 6427 , 6449 , 6451 , 6469 , 6473 , // 105
6481 , 6491 , 6521 , 6529 , 6547 , 6551 , 6553 , 6563 , // 106
6569 , 6571 , 6577 , 6581 , 6599 , 6607 , 6619 , 6637 , // 107
6653 , 6659 , 6661 , 6673 , 6679 , 6689 , 6691 , 6701 , // 108
6703 , 6709 , 6719 , 6733 , 6737 , 6761 , 6763 , 6779 , // 109
6781 , 6791 , 6793 , 6803 , 6823 , 6827 , 6829 , 6833 , // 110
6841 , 6857 , 6863 , 6869 , 6871 , 6883 , 6899 , 6907 , // 111
6911 , 6917 , 6947 , 6949 , 6959 , 6961 , 6967 , 6971 , // 112
6977 , 6983 , 6991 , 6997 , 7001 , 7013 , 7019 , 7027 , // 113
7039 , 7043 , 7057 , 7069 , 7079 , 7103 , 7109 , 7121 , // 114
7127 , 7129 , 7151 , 7159 , 7177 , 7187 , 7193 , 7207 , // 115
7211 , 7213 , 7219 , 7229 , 7237 , 7243 , 7247 , 7253 , // 116
7283 , 7297 , 7307 , 7309 , 7321 , 7331 , 7333 , 7349 , // 117
7351 , 7369 , 7393 , 7411 , 7417 , 7433 , 7451 , 7457 , // 118
7459 , 7477 , 7481 , 7487 , 7489 , 7499 , 7507 , 7517 , // 119
7523 , 7529 , 7537 , 7541 , 7547 , 7549 , 7559 , 7561 , // 120
7573 , 7577 , 7583 , 7589 , 7591 , 7603 , 7607 , 7621 , // 121
7639 , 7643 , 7649 , 7669 , 7673 , 7681 , 7687 , 7691 , // 122
7699 , 7703 , 7717 , 7723 , 7727 , 7741 , 7753 , 7757 , // 123
7759 , 7789 , 7793 , 7817 , 7823 , 7829 , 7841 , 7853 , // 124
7867 , 7873 , 7877 , 7879 , 7883 , 7901 , 7907 , 7919 , // 125
7927 , 7933 , 7937 , 7949 , 7951 , 7963 , 7993 , 8009 , // 126
8011 , 8017 , 8039 , 8053 , 8059 , 8069 , 8081 , 8087 , // 127
8089 , 8093 , 8101 , 8111 , 8117 , 8123 , 8147 , 8161 , // 128
8167 , 8171 , 8179 , 8191 , 8209 , 8219 , 8221 , 8231 , // 129
8233 , 8237 , 8243 , 8263 , 8269 , 8273 , 8287 , 8291 , // 130
8293 , 8297 , 8311 , 8317 , 8329 , 8353 , 8363 , 8369 , // 131
8377 , 8387 , 8389 , 8419 , 8423 , 8429 , 8431 , 8443 , // 132
8447 , 8461 , 8467 , 8501 , 8513 , 8521 , 8527 , 8537 , // 133
8539 , 8543 , 8563 , 8573 , 8581 , 8597 , 8599 , 8609 , // 134
8623 , 8627 , 8629 , 8641 , 8647 , 8663 , 8669 , 8677 , // 135
8681 , 8689 , 8693 , 8699 , 8707 , 8713 , 8719 , 8731 , // 136
8737 , 8741 , 8747 , 8753 , 8761 , 8779 , 8783 , 8803 , // 137
8807 , 8819 , 8821 , 8831 , 8837 , 8839 , 8849 , 8861 , // 138
8863 , 8867 , 8887 , 8893 , 8923 , 8929 , 8933 , 8941 , // 139
8951 , 8963 , 8969 , 8971 , 8999 , 9001 , 9007 , 9011 , // 140
9013 , 9029 , 9041 , 9043 , 9049 , 9059 , 9067 , 9091 , // 141
9103 , 9109 , 9127 , 9133 , 9137 , 9151 , 9157 , 9161 , // 142
9173 , 9181 , 9187 , 9199 , 9203 , 9209 , 9221 , 9227 , // 143
9239 , 9241 , 9257 , 9277 , 9281 , 9283 , 9293 , 9311 , // 144
9319 , 9323 , 9337 , 9341 , 9343 , 9349 , 9371 , 9377 , // 145
9391 , 9397 , 9403 , 9413 , 9419 , 9421 , 9431 , 9433 , // 146
9437 , 9439 , 9461 , 9463 , 9467 , 9473 , 9479 , 9491 , // 147
9497 , 9511 , 9521 , 9533 , 9539 , 9547 , 9551 , 9587 , // 148
9601 , 9613 , 9619 , 9623 , 9629 , 9631 , 9643 , 9649 , // 149
9661 , 9677 , 9679 , 9689 , 9697 , 9719 , 9721 , 9733 , // 150
9739 , 9743 , 9749 , 9767 , 9769 , 9781 , 9787 , 9791 , // 151
9803 , 9811 , 9817 , 9829 , 9833 , 9839 , 9851 , 9857 , // 152
9859 , 9871 , 9883 , 9887 , 9901 , 9907 , 9923 , 9929 , // 153
9931 , 9941 , 9949 , 9967 , 9973 , 10007, 10009, 10037, // 154
10039, 10061, 10067, 10069, 10079, 10091, 10093, 10099, // 155
10103, 10111, 10133, 10139, 10141, 10151, 10159, 10163, // 156
10169, 10177, 10181, 10193, 10211, 10223, 10243, 10247, // 157
10253, 10259, 10267, 10271, 10273, 10289, 10301, 10303, // 158
10313, 10321, 10331, 10333, 10337, 10343, 10357, 10369, // 159
10391, 10399, 10427, 10429, 10433, 10453, 10457, 10459, // 160
10463, 10477, 10487, 10499, 10501, 10513, 10529, 10531, // 161
10559, 10567, 10589, 10597, 10601, 10607, 10613, 10627, // 162
10631, 10639, 10651, 10657, 10663, 10667, 10687, 10691, // 163
10709, 10711, 10723, 10729, 10733, 10739, 10753, 10771, // 164
10781, 10789, 10799, 10831, 10837, 10847, 10853, 10859, // 165
10861, 10867, 10883, 10889, 10891, 10903, 10909, 10937, // 166
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -