search

elliptic-shiho / primefac-fork

a fork of primefac(https://pypi.python.org/pypi/primefac) module
78 stars 12 forks source link

mpqs factorization can get exception doing modular inverse. #3

Closed shortjonescipher closed 6 years ago

shortjonescipher commented 6 years ago

Sometimes mpqs() calls modinv(a, m) with modulus m=1, which is bound to fail. It causes a zero division exception. Here is an example with print('modinv', a, m) inserted in _modinv_gmpy(a, m). I don't know the mpqs algorithm well enough to understand why this happens.

from _primefac import mpqs
mpqs(104540795716322876192089)
modinv 1262 2713
modinv 7360369 43
modinv 7360369 47
modinv 7360369 59
modinv 7360369 83
modinv 7360369 97
modinv 7360369 107
modinv 7360369 113
modinv 7360369 127
modinv 7360369 131
modinv 7360369 139
modinv 7360369 149
modinv 7360369 167
modinv 7360369 199
modinv 7360369 211
modinv 7360369 227
modinv 7360369 229
modinv 7360369 233
modinv 7360369 239
modinv 7360369 241
modinv 7360369 251
modinv 7360369 257
modinv 7360369 271
modinv 7360369 277
modinv 7360369 281
modinv 7360369 283
modinv 7360369 293
modinv 7360369 307
modinv 7360369 313
modinv 7360369 317
modinv 7360369 331
modinv 7360369 379
modinv 7360369 383
modinv 7360369 389
modinv 7360369 401
modinv 7360369 419
modinv 7360369 431
modinv 7360369 433
modinv 7360369 439
modinv 7360369 449
modinv 7360369 457
modinv 7360369 467
modinv 7360369 479
modinv 7360369 491
modinv 7360369 499
modinv 7360369 557
modinv 7360369 563
modinv 7360369 571
modinv 7360369 593
modinv 7360369 601
modinv 7360369 607
modinv 7360369 619
modinv 7360369 631
modinv 7360369 643
modinv 7360369 647
modinv 7360369 661
modinv 7360369 673
modinv 7360369 683
modinv 7360369 691
modinv 7360369 701
modinv 7360369 709
modinv 7360369 719
modinv 7360369 733
modinv 7360369 743
modinv 7360369 751
modinv 7360369 757
modinv 7360369 773
modinv 7360369 823
modinv 7360369 853
modinv 7360369 857
modinv 7360369 859
modinv 7360369 863
modinv 7360369 877
modinv 7360369 881
modinv 7360369 883
modinv 7360369 907
modinv 7360369 929
modinv 7360369 937
modinv 7360369 947
modinv 7360369 971
modinv 7360369 977
modinv 7360369 997
modinv 7360369 1009
modinv 7360369 1021
modinv 7360369 1031
modinv 7360369 1033
modinv 7360369 1051
modinv 7360369 1061
modinv 7360369 1091
modinv 7360369 1097
modinv 7360369 1103
modinv 7360369 1117
modinv 7360369 1129
modinv 7360369 1151
modinv 7360369 1181
modinv 7360369 1187
modinv 7360369 1193
modinv 7360369 1201
modinv 7360369 1217
modinv 7360369 1223
modinv 7360369 1229
modinv 7360369 1231
modinv 7360369 1237
modinv 7360369 1249
modinv 7360369 1259
modinv 7360369 1279
modinv 7360369 1289
modinv 7360369 1301
modinv 7360369 1303
modinv 7360369 1307
modinv 7360369 1327
modinv 7360369 1361
modinv 7360369 1367
modinv 7360369 1381
modinv 7360369 1399
modinv 7360369 1423
modinv 7360369 1427
modinv 7360369 1429
modinv 7360369 1439
modinv 7360369 1447
modinv 7360369 1459
modinv 7360369 1487
modinv 7360369 1489
modinv 7360369 1499
modinv 7360369 1511
modinv 7360369 1543
modinv 7360369 1559
modinv 7360369 1583
modinv 7360369 1597
modinv 7360369 1601
modinv 7360369 1607
modinv 7360369 1609
modinv 7360369 1619
modinv 7360369 1637
modinv 7360369 1657
modinv 7360369 1663
modinv 7360369 1723
modinv 7360369 1747
modinv 7360369 1759
modinv 7360369 1789
modinv 7360369 1811
modinv 7360369 1831
modinv 7360369 1861
modinv 7360369 1877
modinv 7360369 1879
modinv 7360369 1901
modinv 7360369 1949
modinv 7360369 1979
modinv 7360369 1987
modinv 7360369 1993
modinv 7360369 1997
modinv 7360369 2017
modinv 7360369 2027
modinv 7360369 2053
modinv 7360369 2069
modinv 7360369 2081
modinv 7360369 2087
modinv 7360369 2099
modinv 7360369 2131
modinv 7360369 2137
modinv 7360369 2141
modinv 7360369 2161
modinv 7360369 2207
modinv 7360369 2213
modinv 7360369 2243
modinv 7360369 2267
modinv 7360369 2273
modinv 7360369 2297
modinv 7360369 2309
modinv 7360369 2347
modinv 7360369 2351
modinv 7360369 2383
modinv 7360369 2399
modinv 7360369 2411
modinv 7360369 2437
modinv 7360369 2521
modinv 7360369 2539
modinv 7360369 2549
modinv 7360369 2557
modinv 7360369 2591
modinv 7360369 2593
modinv 7360369 2609
modinv 7360369 2621
modinv 7360369 2633
modinv 7360369 2663
modinv 7360369 2687
modinv 7360369 2689
modinv 7360369 2693
modinv 2713 1

Traceback (most recent call last):
  File "<pyshell#60>", line 1, in <module>
    mpqs(104540795716322876192089)
  File "C:\Python27\lib\site-packages\_primefac\_factor_algo\_mpqs.py", line 105, in mpqs
    inv_A = modinv(A // g, p // g) * g
  File "C:\Python27\lib\site-packages\_primefac\_arith.py", line 169, in _modinv_gmpy
    return int(_util.gmpy.invert(a, m))
ZeroDivisionError: invert() no inverse exists
elliptic-shiho commented 6 years ago

Thanks, I fixed it and added test case to Travis CI.

(BTW, I couldn't reproduce this behavior... (Ubuntu 16.04.1 w/ Python 2.7.14, gmpy 1.17, gmpy2 2.0.8))

> python
Python 2.7.14 (default, Jan 27 2018, 18:58:58) 
[GCC 5.4.0 20160609] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import gmpy, gmpy2
>>> gmpy.invert(2713, 1)
mpz(0)
>>> gmpy2.invert(2713, 1)
mpz(0)
>>>