search

bbuhrow / yafu

Automated integer factorization
197 stars 30 forks source link

Yafu 2.11.0 randomly dies running SIQS #27

Open alexhiggins732 opened 1 year ago

alexhiggins732 commented 1 year ago

This is a new bug in 2.11.0 since the previous version I used (2.6.0). When running SIQS, either from an interactive session or from the command line, yafu silently dies. When running from the command line Yafu exists without returning a value. In an interactive session Yafu just unexpectedly quits.

How to reproduce From the command line or an interactive session execute siqs(rsa(n)). I found the bug is more repeateble for n >= 195 and happens more often the higher the bit count. Some times Yafu runs siqs as expected, other times it silently dies.

Example - Running yafu siqs(rsa(195)) three different times resulted in 2 silent crash and one expected factorization:

C:\Users\alexh\Downloads>yafu-x64-2.11.0 siqs(rsa(195))
warning: could not open yafu.ini, no options parsed

starting SIQS on c59: 29143523039182981214859189625921499361971313872610326847221

==== sieving in progress (1 thread):    3360 relations needed ====
====           Press ctrl-c to abort and save state           ====

C:\Users\alexh\Downloads>yafu-x64-2.11.0 siqs(rsa(195))
warning: could not open yafu.ini, no options parsed

starting SIQS on c59: 26542706886245374309651514556213335247761359832034606238079

==== sieving in progress (1 thread):    3360 relations needed ====
====           Press ctrl-c to abort and save state           ====
3376 rels found: 1843 full + 1533 from 15236 partial, (15697.58 rels/sec)

building matrix with 3376 columns
SIQS elapsed time = 1.1560 seconds.

***factors found***

P29 = 53526853725569577176054134427
P30 = 495876462725213808451633853677

ans = 1

C:\Users\alexh\Downloads>yafu-x64-2.11.0 siqs(rsa(195))
warning: could not open yafu.ini, no options parsed

starting SIQS on c59: 31251366925945375290978313044853078877737298580075620721179

==== sieving in progress (1 thread):    3360 relations needed ====
====           Press ctrl-c to abort and save state           ====

C:\Users\alexh\Downloads>

An example of a silent crash from an interactive session:

C:\Users\alexh\Downloads>yafu-x64-2.11.0
warning: could not open yafu.ini, no options parsed

YAFU Version 2.11
Built with Microsoft Visual Studio 1934 and Intel Compiler 2021
Using GMP-ECM 7.0.6-dev, Powered by MPIR 3.0.0
Detected AMD Ryzen 7 2700X Eight-Core Processor
Detected L1 = 32768 bytes, L2 = 16777216 bytes, CL = 64 bytes
CPU features enabled: SSE41 AVX2 BMI2
Using 1 random witness for Rabin-Miller PRP checks
Cached 664579 primes; max prime is 9999991
Could not parse yafu.ini from C:\Users\alexh\Downloads

===============================================================
======= Welcome to YAFU (Yet Another Factoring Utility) =======
=======             bbuhrow@gmail.com                   =======
=======     Type help at any time, or quit to quit      =======
===============================================================

>> siqs(rsa(195))

starting SIQS on c59: 34026305554134277891529831948966800036747540051673059285057

==== sieving in progress (1 thread):    3360 relations needed ====
====           Press ctrl-c to abort and save state           ====

C:\Users\alexh\Downloads>

A print screen from the above:

image

An example of a failed run from the command line followed by a successful run: image

At first glance it appears the failure are random.

Another failure: image

Factor.log shows no useful information about the failure:

05/15/23 23:40:55, ****************************
05/15/23 23:40:55, Starting factorization of 47237163253435009887901865241423095913427115588142655298191
05/15/23 23:40:55, using pretesting plan: normal
05/15/23 23:40:55, no tune info: using qs/gnfs crossover of 95 digits
05/15/23 23:40:55, no tune info: using qs/snfs crossover of 95 digits
05/15/23 23:40:55, ****************************
05/15/23 23:40:55, rho: x^2 + 3, starting 1000 iterations on C59
05/15/23 23:40:55, rho: x^2 + 2, starting 1000 iterations on C59
05/15/23 23:40:55, rho: x^2 + 1, starting 1000 iterations on C59
05/15/23 23:40:55, pm1: starting B1 = 150K, B2 = gmp-ecm default on C59
05/15/23 23:40:55, current ECM pretesting depth: 0.000000
05/15/23 23:40:55, scheduled 30 curves at B1=2000 toward target pretesting depth of 18.153846
05/15/23 23:40:55, Finished 30 curves using GMP-ECM method on C59 input, B1=2k, B2=gmp-ecm default
05/15/23 23:40:55, current ECM pretesting depth: 15.177725
05/15/23 23:40:55, scheduled 45 curves at B1=11000 toward target pretesting depth of 18.153846
05/15/23 23:40:56, Finished 45 curves using GMP-ECM method on C59 input, B1=11k, B2=gmp-ecm default
05/15/23 23:40:56, final ECM pretested depth: 18.218266
05/15/23 23:40:56, scheduler: switching to sieve method
05/15/23 23:40:56, starting SIQS on c59: 47237163253435009887901865241423095913427115588142655298191
05/15/23 23:40:56, random seed: 9627079694242928434
05/15/23 23:40:58, 
05/15/23 23:40:58, ****************************
05/15/23 23:40:58, Starting factorization of 31430849781949261943379453391308604171167895827412108954201

Additional information: OS: Windows 11, fully patched. Running from windows console, but WSL 2 installed with latest Ubuntu, along with up to date Visual Studio 2022, latest Dotnet core framework and recent c/c++ runtimes.

alexhiggins732 commented 1 year ago

As a side note, Yafu used to "play nice" and set it's thread priority to below normal. Now when launching with the maximum threads on my OS, my system becomes unresponsive, and I need to manually go into task manager and set the process priority to below normal. I wonder if below normal can be the default, with a switch to set process priority to normal or higher as an optional setting.