"Ben"
Feb 2007
3·1,193 Posts

Quote:
Originally Posted by Shaopu Lin
When I factored 1096^32+1 by yafu1.04, it crashed.
Code:
math@linux0rdr:~/Desktop/application/yafu> gdb yafu
GNU gdb 6.8
Copyright (C) 2008 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law. Type "show copying"
and "show warranty" for details.
This GDB was configured as "x86_64suselinux"...
(gdb) run
Starting program: /usr/local/bin/yafu
[Thread debugging using libthread_db enabled]
12/06/08 19:19:13 v1.04 @ linux0rdr,
Initializing with Tom's Fast Math (x8664 asm)...
cached 664581 primes. pmax = 10000079
detected cpu 6, with L1 = 32768 bytes, L2 = 6291456 bytes
======= Welcome to YAFU (Yet Another Factoring Utility) =======
======= bbuhrow@gmail.com =======
======= Type help at any time, or quit to quit =======
factor(1096^32+1)
factoring 18790473878519993984890398730678350603395072493250843267866231345265081616078243538507497331490817
div: primes less than 10000
rho: x^2 + 1, 1000 iterations, input has 324 bits , elapsed time = 0.0200
rho: x^2 + 3, 1000 iterations, input has 324 bits , elapsed time = 0.0200
rho: x^2 + 2, 1000 iterations, input has 324 bits , elapsed time = 0.0200
pp1: base 1583572992, B1 = 20K, B2 = 1M, input has 324 bits , processed < 1000003, Stg1 = 0.0400, Stg2 = 0.0400
pm1: base 2303465472, B1 = 100K, B2 = 5M, input has 324 bits , processed < 10000, processed < 5000011, Stg1 = 0.0800, Stg2 = 0.1700
ecm: curve 25, sigma = 2260160512, input has 324 bits, processed < 199999
ecm: curve 90, sigma = 1904388096, input has 324 bits, processed < 1099997
ecm: curve 200, sigma = 1798552064, input has 324 bits, processed < 4999999
starting SIQS on c98: 18790473878519993984890398730678350603395072493250843267866231345265081616078243538507497331490817
restarting siqs from saved data set
96479 relations found: 24595 full + 71884 from 1370973 partial
sieve time = 0.0000, relation time = 0.0000, poly_time = 0.0000
trial division touched 0 sieve locations out of 0
size of relation set in memory = 0 bytes
QS elapsed time = 1.2400 seconds.
==== post processing stage (msieve1.38) ====
begin with 1395567 relations
reduce to 244773 relations in 10 passes
attempting to read 244773 relations
[New Thread 0x7fd3f29346f0 (LWP 5596)]
Program received signal SIGSEGV, Segmentation fault.
[Switching to Thread 0x7fd3f29346f0 (LWP 5596)]
zFree (num=0x7ffffa985260) at arith0.c:84
84 arith0.c: No such file or directory.
in arith0.c
(gdb) bt full
#0 zFree (num=0x7ffffa985260) at arith0.c:84
No locals.
#1 0x000000000044b90e in process_poly_a (a=<value optimized out>,
fb=<value optimized out>, n=0x65bf80, max_s=20, conf=0x7ffffa96d120)
at relation.c:724
poly = <value optimized out>
tmp = {val = 0x6b0760, alloc = 100, size = 1, type = 3}
Bl = <value optimized out>
maxB = 4096
j = 4097
#2 0x000000000044cacc in qs_filter_relations (conf=0x6b0dc0, from_file=1)
at relation.c:1384
r = (siqs_r *) 0x132
obj = (msieve_obj *) 0x6746d0
hashtable = (uint32 *) 0x7fd3efff1010
table = (cycle_t *) 0x7fd3eaddb010
num_derived_poly = <value optimized out>
final_poly_index = (uint32 *) 0x68ad80
num_relations = 244773
num_cycles = <value optimized out>
num_poly = 10000
cycle_list = <value optimized out>
relation_list = (siqs_r *) 0x7fd3e5b5d010
Type <return> to continue, or q <return> to quit
i = 0
passes = <value optimized out>
start = <value optimized out>
curr_a_idx = 0
curr_rel = 4294967295
curr_expected = 0
curr_saved = 0
curr_cycle = <value optimized out>
total_poly_a = 306
cycle_bins = {4063078272, 32723, 10, 0, 4026904753, 22103, 1308622848,
2929712, 4167989992}
buf = "A 0x114b591a26ba3f64dee948fd387afbf895b1f\n\000895fd2031d278531d11", '0' <repeats 22 times>, "11\n\0008 1711 40d5 L 28003cd 28243a5\n\000\n\000\000f7\n\0009e26c9\n\000\000\0003\n\0005\n\000\000\0001\n\000b\n\000 1 519666d\n\000f\000\000\000\000\000\200�e\000\000\000\000\000\220�\226��\177\000\000�_���\177\000\000\b\000\000\000@\000\000\000z\211���\177\000\000��\226�"...
tmpint = 5658608
last_id = 0
#3 0x000000000041195e in SIQS (n=0x65bf80, override_B=<value optimized out>,
override_L=<value optimized out>, override_M=<value optimized out>)
at SIQS.c:924
rlist = <value optimized out>
relation_list = <value optimized out>
Type <return> to continue, or q <return> to quit
fb = <value optimized out>
fb_sieve_p = <value optimized out>
fb_sieve_n = <value optimized out>
poly = <value optimized out>
polys = <value optimized out>
lp_bucket_p = {num = {4294967192, 4294967295, 4204181072, 32767,
4069738224, 32723, 1, 0, 4204182896, 32767, 4063078272, 32723, 0, 0,
4204182816, 32767, 1546188227, 1069925007, 0, 0, 24, 0, 0, 48, 4060774223,
32723, 4204182664, 46, 0, 0, 4204180536, 0, 0, 0, 4204182640, 0,
4204180576, 32767, 4204182712, 0, 1, 6, 4204180584, 32767, 6, 0, 0, 4, 4,
2147483647, 4060055930, 32723, 0, 0, 4063078272, 32723, 4545343, 0, 31, 0,
4069965824, 32723, 4060055002, 32723, 0, 0, 31, 0, 4545343, 0, 1, 0,
4063078272, 32723, 4060055829, 32723, 0, 0, 4060055353, 32723, 30, 0, 1,
0, 4204183104, 32767, 4063078272, 32723, 4545343, 0, 4545344, 0, 30, 0,
4059873796, 32723, 1, 2, 0, 0, 0, 32767, 4204182848, 32767, 10, 2816,
4204182928, 32767, 4204182968, 32767, 4204183000, 32767, 4204182992,
32767, 4204182896, 32767, 32, 0, 4204183072, 32767, 4545315, 0,
1660944384, 4204182769, 4204181824, 32767, 4069738224, 32723, 0, 0,
4204183120, 32767, 4545315, 0, 0, 4204182817, 7, 0, 0, 0, 0, 0, 4545264,
4294967294, 0, 0, 4294967295, 4294967295, 4545342, 0, 4545324, 0, 0, 0,
4545264, 0, 0, 0, 4294967295, 4294967295, 4545342, 0, 4545324, 0, 0, 0,
4204182824, 32767, 1, 2, 0, 1, 0, 0, 0, 0, 10, 0 <repeats 11 times>,
317243936, 2242921186, 1902413604, 3254584972, 117712992, 2732937580,
Type <return> to continue, or q <return> to quit
1711276036, 0, 0, 0, 0, 0, 0...}, fb_bounds = {0 <repeats 14 times>,
4060738624, 32723, 4204185072, 32767, 4204185632, 32767, 1, 0, 4059863990,
32723, 0, 0, 0, 0, 0, 0, 4204185240, 32767, 4204185696, 32767, 0, 0,
4204185088, 32767, 4059898389, 32723, 0, 0, 4, 0, 858992176, 12336,
4059898194, 32723, 4204185632, 32767, 4204185616, 32767, 4204185696,
32767, 48, 46, 51, 51, 48, 48, 0, 0, 12, 0, 4204185696, 32767, 48, 46, 48,
48, 48, 48, 0, 0, 0, 0, 0, 0, 0, 0, 859004928, 858993459, 13,
0 <repeats 13 times>, 286720000, 0, 0, 0},
logp = '\0' <repeats 16 times>, "\037\205�Q�\036�?�\033���\177", '\0' <repeats 26 times>, "z\211���\177\000\000\000\000\000\000\000\000\000\000\020�\226��\177\000\000\230���������\226��\177\000\000�F\223�", num_slices = 32723,
list = 0x0}
lp_bucket_n = {num = {0 <repeats 1000 times>}, fb_bounds = {0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 4060738624, 32723, 4204180544, 32767, 4204181104,
32767, 1, 0, 4059863990, 32723, 0, 0, 4060738624, 32723, 4204180592,
32767, 4204181152, 32767, 1, 0, 4059863990, 32723, 6, 0, 4059899067,
32723, 0, 0, 4204180760, 32767, 5, 0, 4204181216, 32767, 6, 0, 4059899067,
32723, 4060742232, 32723, 4, 0, 925969968, 12336, 4059898194, 32723,
4204181152, 32767, 4204181136, 32767, 4204181216, 32767, 48, 46, 49, 55,
48, 48, 0, 0, 0, 0, 0, 0, 0, 0, 49152, 0, 128, 0, 0, 0, 0, 0, 0, 0, 0, 0,
2576998400, 2576980377, 13, 0, 0, 0, 0, 0, 0, 0, 0, 0},
logp = "{\024�G�z�?�\033���\177\000\000\000\200m\r", '\0' <repeats 28 times>, "��(\\\217��?�\033���\177\000\000\230������� �\226��\177\000\000�F\223��\177\000Type <return> to continue, or q <return> to quit
\000\001\000\000\000\000\000\000\000@�\226�", num_slices = 32767, list = 0x0}
conf = {obj = 0x6746d0, n = 0x65bf80, multiplier = 6668160,
sieve_block_size = 0,
sieve_array = 0xffffffffffffffd0 <Address 0xffffffffffffffd0 out of bounds>,
factor_base = 0x65e0a0, fb_size = 40, num_sieve_blocks = 0, poly_block = 40,
fb_block = 0, sieve_small_fb_start = 88, sieve_large_fb_start = 0,
tf_small_recip1_cutoff = 96, tf_small_recip2_cutoff = 0,
tf_med_recip1_cutoff = 6746448, tf_med_recip2_cutoff = 0,
tf_large_cutoff = 4204188288, cutoff1 = 32767, cutoff2 = 4204188256,
modsqrt_array = 0x65bf80, target_a = {val = 0x96371f543b905fcd, alloc = 5,
size = 6, type = 0}, a_bits = 1389045152, total_poly_a = 306,
poly_a_list = 0xbfce30, poly_list = 0xb3fc90, poly_list_alloc = 0,
poly_info = 0x65de50, curr_a = {val = 0x6cb210, alloc = 100, size = 3,
type = 3}, curr_b = 0x7ffffa96d260, bpoly_alloc = 4060079846,
next_poly_action = 0x7ffffa96d2c0 " �f", num_poly_factors = 4302479,
factor_bounds = {0, 3, 0, 4204188464, 32767, 4204188496, 32767, 4204188464,
32767, 6746544, 0, 100, 12, 3, 0, 6785856, 0, 6745728, 0, 100, 1, 3, 0,
848, 0}, poly_tmp_b = 0x6cb540, poly_b_array = 0x600000064,
large_prime_max = 3, max_fb2 = {val = 0xbfc7d0, alloc = 100, size = 1,
type = 3}, large_prime_max2 = {val = 0xbfcb00, alloc = 100, size = 1,
type = 3}, relation_list = 0x100000064, rlist = 0x66f1a0,
num_relations = 24595, cycle_list = 0x66e820, num_cycles = 1370973,
cycle_table = 0x7fd3eaddb010, cycle_table_size = 1479893,
Type <return> to continue, or q <return> to quit
cycle_table_alloc = 2560000, cycle_hashtable = 0x7fd3efff1010,
components = 180803, vertices = 1479892}
tmp = {val = 0x66d740, alloc = 100, size = 1, type = 3}
tmp2 = {val = 0x66da70, alloc = 100, size = 3, type = 3}
tmp3 = {val = 0x66dda0, alloc = 100, size = 1, type = 3}
sqrt_n = {val = 0xbfc170, alloc = 100, size = 3, type = 3}
target_a = {val = 0xbfc4a0, alloc = 100, size = 1, type = 3}
apoly = (z *) 0x6c4900
Bl = <value optimized out>
cycle_list = <value optimized out>
num_cycles = <value optimized out>
bitfield = (uint64 *) 0x0
obj = <value optimized out>
factor_list = {num_factors = 0, final_factors = {0x66e820, 0x0,
0x66e820, 0x3fd51eb851eb851f, 0x0, 0x18, 0x7fd300000000, 0x7fd3f20a7f4f,
0x2e00000002, 0x0, 0x66e820, 0x0, 0x454790, 0x7ffffa96c5e0, 0xf1fcc204,
0x600000001, 0x7ffffa96c5e8, 0x6, 0x400000000, 0x7fffffff00000004,
0x66007fff00000000, 0x0, 0xfa96ce78, 0x7ffffa96c610, 0x7ffffa96c650,
0x7ffffa96c690, 0x2, 0x0, 0x66fffffffb, 0x7fff00000001, 0x7fd3f29346f0,
0x0, 0x2, 0x0, 0x7fd3f22da780, 0x7ffffa96cec1, 0x7fd3f20a18f0, 0xe,
0x7fd3f1feebcb, 0x4559ca, 0x0, 0x7ffffa96cfe0, 0x7fd3f22da780, 0x455929,
0x455929, 0x17, 0x7fd3f1fcc204, 0xb000045478d, 0x7ffffa96cf10,
0x7ffffa96cf38, 0x7ffffa96cf58, 0xb00fa96cf50, 0x7ffffa96cf30,
Type <return> to continue, or q <return> to quit
0x7ffffa96cf58, 0x7ffffa96cf78, 0x7ffffa96cf70, 0x7ffffa96cf10,
0x7ffffa96cac0, 0x7fd3f29346f0, 0x0, 0x7ffffa96cfd0, 0x7ffffa96cae0,
0x7fd3f29346f0, 0xa, 0x7ffffa96cff0, 0x455918, 0xfa96cec1ffffffff, 0x7,
0x7ffffa96cb8b, 0x7ffffa96cad0, 0x7ffffa96cba0, 0x100, 0x7ffffa96ca80,
0x0, 0xffffffffffffffff, 0x4559c9, 0x4559c5, 0x0, 0xffffffffffffffff,
0x455928, 0x455926, 0x0, 0x7ffffa96cec8, 0x200000000, 0x100000000, 0x0,
0x0, 0xa, 0x0, 0x0, 0x0, 0x0, 0x0, 0x7fd3f22da520, 0x7fd3f22d7d40,
0x2fa96ca40, 0xa7543cfc8, 0x7fd3f20a7f4f, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0,
0x100, 0x1, 0x65c090, 0x675a08, 0x4559cf, 0x0, 0x0, 0x0, 0x455929,
0x7fd3f20a7827, 0x400000001, 0x7ffffa96cea8, 0x7ffffa96cec1,
0xb5b018a5adfe9d3f, 0x13ab91639, 0x7ffffa96cec8, 0x56931410043cfc8, 0x0,
0x65c090, 0x7ffffa96d250, 0x600000007, 0x7ffffa96cb30, 0x43cfc8, 0x0,
0x65c090, 0x66f120, 0x600000007, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0,
0x2695ab716971bde9, 0x1d013c1ad8dbc13f, 0x38632ecf7cb651e4,
0x208cd5a7b497e124, 0xea12240fcfc97043, 0x6, 0x0, 0x0, 0x0, 0x73ffffff,
0x1, 0x7fffffffffff, 0x0, 0x7ffffa96ce1b, 0x7ffffa96cd60, 0x7ffffa96ce30,
0x455b4e, 0x455b46, 0x7fd3f22eead0, 0x7ffffa96ccc0, 0x0, 0x0,
0x3000000018, 0x7ffffa96cec0, 0x7ffffa96ce00, 0x100000000, 0x0, 0x65b470,
0x675070, 0x66f138, 0x6764d0, 0x0, 0x0, 0x7ffffa96c801, 0x0, 0x65e29d,
0x0, 0x65e29c, 0x65e29c, 0x7ffffa96cde0, 0x7fd3f20a7823, 0x7ffffa96cfa0,
0x7ffffa96cf40, 0x7fd3f1feffa5, 0xfbad8001, 0x65e29d, 0x65e29d, 0x65e29c,
0x65e29c, 0x65e29c, 0x65e29c, 0x65e29c, 0x65e29d, 0x0, 0x0,
0x7fd3f201b4f6, 0x0, 0x0, 0x0, 0x0, 0x660000, 0x0, 0x66f120...}}
Type <return> to continue, or q <return> to quit
num_apoly = 0
tot_poly = 0
apoly_alloc = 0
numB = 0
maxB = 0
num_r = 96479
rootupdates = <value optimized out>
firstroots1 = <value optimized out>
firstroots2 = <value optimized out>
t_time1 = 0
t_time2 = 0
t_time3 = 0
start = 137700000
stop = <value optimized out>
start1 = 138940000
stop1 = <value optimized out>
start2 = <value optimized out>
stop2 = <value optimized out>
start3 = <value optimized out>
stop3 = <value optimized out>
totaltime_start = 137700000
totaltime_stop = <value optimized out>
update_start = 0
Type <return> to continue, or q <return> to quit
update_stop = <value optimized out>
update_time = 0
sum = <value optimized out>
avg = <value optimized out>
i = <value optimized out>
charcount = <value optimized out>
uni = 0
mul = 17
j = <value optimized out>
j2 = <value optimized out>
pmax = 2644769
cutoff = 383491505
last_numfull = 0
last_numpartial = 0
num_expected = <value optimized out>
sieve_interval = <value optimized out>
check_total = 0
check_inc = 0
num = 0
digits_n = 98
sieve = <value optimized out>
closnuf = <value optimized out>
small_bits = <value optimized out>
Type <return> to continue, or q <return> to quit
sieve_log = (FILE *) 0x66d500
str_n = {
s = 0x66ed90 "18790473878519993984890398730678350603395072493250843267866231345265081616078243538507497331490817", nchars = 99, alloc = 1024}
buf = '\0' <repeats 72 times>, "��A\000\000\000\000\000\006\t\000\000\000\000\000\000l\225���\177\000\000��A\000\000\000\000\000\002\000\000\000\000\000\000\000`\022\002\000\000\000\000\000�\035�\000\000\000\000\000\000���\177\000\000B\017\000��\177\000\000��f\000\000\000\000\000\000���\177\000\000\000\000\000\000\000\000\000\000\020�\226��\177\000\000��\226��\177\000\000��\226��\177\000\000��\226��\177\000\000�����\177\000\000V\000\000\000\000\000\000\000��A\000\000\000\000\000\0004999999\000\000\000\024\000\000\000\000`\226���\177\000\000z\211���\177\000\000\000\000\000\000\000\000"...
no_dump = 1
#4 0x00000000004029c4 in factor (b=0x65bf80) at factor_common.c:406
i = <value optimized out>
next = 12288
done = 1
tmp1 = 11000
tmp2 = 1100000
flog = (FILE *) 0x2af8
#5 0x0000000000404322 in feval (func=12288, nargs=1) at calc.c:788
mp1 = {val = 0x66c100, alloc = 100, size = 1, type = 3}
mp2 = {val = 0x66c430, alloc = 100, size = 1, type = 3}
Type <return> to continue, or q <return> to quit
mp3 = {val = 0x66c760, alloc = 100, size = 1, type = 3}
tmp1 = {val = 0x66ca90, alloc = 100, size = 1, type = 3}
tmp2 = {val = 0x66cdc0, alloc = 100, size = 1, type = 3}
str = {s = 0x66d0f0 "", nchars = 1, alloc = 1024}
i = <value optimized out>
n64 = <value optimized out>
j = <value optimized out>
k = <value optimized out>
start = <value optimized out>
stop = <value optimized out>
#6 0x00000000004057eb in calc (in=0x7ffffa96d650) at calc.c:622
i = 5
retval = <value optimized out>
na = 1
func = 7
j = 1
stk = {elements = 0x665130, num = 0, size = 20, top = 1, type = 0}
tmp = <value optimized out>
post = <value optimized out>
tokens = (char **) 0x664dc0
token_types = <value optimized out>
num_tokens = 6
varstate = <value optimized out>
Type <return> to continue, or q <return> to quit
tmpz = {val = 0x66b9c0, alloc = 100, size = 1, type = 3}
#7 0x0000000000409f98 in main (argc=<value optimized out>,
argv=<value optimized out>) at driver.c:340
i = <value optimized out>
limit = 10000320
tt = 1228562353
s = <value optimized out>
str = {s = 0x65d420 "factor(1096^32+1)", nchars = 18, alloc = 1024}
tmp = {val = 0x65e910, alloc = 100, size = 1, type = 3}
cpu = <value optimized out>
nooutput = 0
offset = <value optimized out>
slog = 1
do_once = 0
nfile = <value optimized out>
logfile = (FILE *) 0x664b80
in = (FILE *) 0x7fd3f22da6a0
hnamestr = "\001\000\000\000N0�,�d\223��\177\000\000x�\226
cmd = "rm \001\000ame > \001\000\000\000\000�\000\000\000\001\000\000\000\200j\223��\177\000\000X�\226��\177\000"
(gdb)

This completed fine for me using the 64 bit linux version. Not sure what's going on, but I'll look into it soon when I have some time.
Code:
12/06/08 09:21:18 v1.04 @ tion,
Initializing with Tom's Fast Math (x8664 asm)...
cached 78504 primes. pmax = 1000099
detected cpu 6, with L1 = 32768 bytes, L2 = 4194304 bytes
starting SIQS on c98: 18790473878519993984890398730678350603395072493250843267866231345265081616078243538507497331490817
restarting siqs from saved data set
5010 relations found: 4277 full + 733 from 242141 partial
==== sieve params ====
n = 98 digits, 328 bits
factor base: 96407 primes (max prime = 2644769)
single large prime cutoff: 383491505 (145 * pmax)
double large prime range from 44 to 52 bits
double large prime cutoff: 2823321571947548
using 13 large prime slices of factor base
sieve interval: 32 blocks of size 32768
polynomial A has ~ 13 factors
using multiplier of 17
using small prime variation correction of 10 bits
trial factoring cutoff at 106 bits
==== sieving in progress (ctrlc to abort) ====
96488 relations found: 24337 full + 72151 from 1376274 partial, using 1033283 polys
sieve time = 3622.2900, relation time = 1368.2600, poly_time = 4149.0200
trial division touched 36094827 sieve locations out of 2166951510016
size of relation set in memory = 0 bytes
QS elapsed time = 9164.8800 seconds.
==== post processing stage (msieve1.38) ====
begin with 1400610 relations
reduce to 245650 relations in 11 passes
attempting to read 245650 relations
error, skipping relation 52508
failed to read relation 52460
error, skipping relation 55169
failed to read relation 55121
error, skipping relation 93811
failed to read relation 93763
error, skipping relation 119589
failed to read relation 119541
recovered 245646 relations
recovered 222990 polynomials
attempting to build 96483 cycles
found 96483 cycles in 6 passes
distribution of cycle lengths:
length 1 : 24337
length 2 : 17771
length 3 : 16685
length 4 : 13149
length 5 : 9436
length 6 : 6244
length 7 : 3799
length 9+: 5062
largest cycle: 19 relations
matrix is 96407 x 96483 (27.7 MB) with weight 6481896 (67.18/col)
sparse part has weight 6481896 (67.18/col)
filtering completed in 3 passes
matrix is 91621 x 91685 (26.5 MB) with weight 6214768 (67.78/col)
sparse part has weight 6214768 (67.78/col)
saving the first 48 matrix rows for later
matrix is 91573 x 91685 (18.4 MB) with weight 5011598 (54.66/col)
sparse part has weight 3905510 (42.60/col)
matrix includes 64 packed rows
using block size 36674 for processor cache size 4096 kB
commencing Lanczos iteration
memory use: 15.7 MB
lanczos halted after 1450 iterations (dim = 91570)
recovered 16 nontrivial dependencies
Lanczos elapsed time = 46.6800 seconds.
Sqrt elapsed time = 2.4700 seconds.
Total elapsed time = 9214.0300 seconds.
***factors found***
PRP50 = 21441220812095339221362249659178991821433335027457
PRP48 = 876371454927603000740623088935368770053503412481
ans = 1
