diff options
| author | Jack Lloyd <[email protected]> | 2016-01-29 14:35:30 -0500 |
|---|---|---|
| committer | Jack Lloyd <[email protected]> | 2016-02-01 06:14:44 -0500 |
| commit | d7471d1d3bbb8b2ed454cb2e2ae15a7d178f2770 (patch) | |
| tree | 8fe6b3e74fead0ff32fc956e50f68c821bdc17a7 /src/tests/data | |
| parent | 61f919adb8bb3e0ba225f1758d679f775df876ba (diff) | |
Fix (nearly) infinite loop in RESSOL (modular square root).
It first computed the first i for q**(2**i) == 1, then checked that i
was smaller than s. Given a composite modulus (for which the algorithm
does not work), the loop might do a very large amount of work before
returning the failure.
Diffstat (limited to 'src/tests/data')
| -rw-r--r-- | src/tests/data/bigint.vec | 13 |
1 files changed, 13 insertions, 0 deletions
diff --git a/src/tests/data/bigint.vec b/src/tests/data/bigint.vec index bba83deb6..2445c8de4 100644 --- a/src/tests/data/bigint.vec +++ b/src/tests/data/bigint.vec @@ -2580,3 +2580,16 @@ IsPrime = 0 Value = 0x53251 IsPrime = 0 +[RESSOL] +Input = 5 +Modulus = 11 +Output = 4 + +Input = 5 +Modulus = 6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151 +Output = 5128001483797946816458955548662741861156429216952843873274631897232136999791540518339021539968609345897897688700798659762992302941280478805021587896033442584 + +# Input and composite modulus which would previously cause a (nearly) infinite loop +Input = 4 +Modulus = 6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057149 +Output = -1 |