Dependencies and cycles - Page 2

Batalov · 2011-06-02, 06:00

gcc version shouldn't be a problem.

To generate just a few relations you may use either msieve alone (first generate any polynomial in -np mode, then sieve by its own line sieve), or by ggnfs suite - it contains a frightening lattice siever by Kleinjung+Franke. Because you only need a few relations, you will easily get away by setting the FB and LP limits low.

Once you will get relations, note that their factorizations are by convention not listing the factors under 1000 (iirc). But these are easily reconstructed for example in Pari/GP shell or a one-off c+GMPlib (or perl+Math::BigInt) program. (Or you can fiddle with the guts of either gnfs-lasieve4e.c or msieve relation.c, again iirc, in order to print out all factors.)

jasonp · 2011-06-02, 20:39

Note that even a line sieve would have difficulty with 1024-bit GNFS; I tried with an older version of the current line sieve, and even with a factor base limit of 2^32 it only found three relations.

Sleepy · 2011-06-07, 01:54

I see.. I managed to get the sieving of RSA-768 to work on another PC. Thanks a lot for the help! =)

Sleepy · 2011-06-10, 06:49

Sorry another question, is it possible to remove the 308 digit limit to conduct some tests? i tried to edit some parts of the code but i think i am missing something crucial.

Batalov · 2011-06-10, 06:53

You need to increase the
#define MAX_MP_WORDS 32
in mp.h to something bigger.
The other places you probably already found.

Sleepy · 2011-06-10, 08:07

Hmm, i tried changing that to 34 or 40 but it still doesnt work. The error i got was:
warning: NFS input not found in factor base file

Any idea why i got that?

Batalov · 2011-06-10, 08:18

include/common.h:#define LINE_BUF_SIZE 300

Sleepy · 2011-06-10, 09:16

Thanks a lot!! I can run it now!! So that was the problem.. =D

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Too few cycles error	cardmaker	Factoring	4	2016-12-29 15:52
"lanczos error: only trivial dependencies found" with massive oversieving	eigma	Msieve	21	2015-05-28 03:27
3n + 1 cycles for n = 2^57,885,161-1	Unregistered	Information & Answers	7	2013-02-16 02:24
Cheapest CPU cycles?	siegert81	Hardware	17	2010-12-27 18:00
CPU cycles	Unregistered	Information & Answers	0	2007-07-19 12:24

2011-06-02, 06:00	#12
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2505₁₆ Posts	gcc version shouldn't be a problem. To generate just a few relations you may use either msieve alone (first generate any polynomial in -np mode, then sieve by its own line sieve), or by ggnfs suite - it contains a frightening lattice siever by Kleinjung+Franke. Because you only need a few relations, you will easily get away by setting the FB and LP limits low. Once you will get relations, note that their factorizations are by convention not listing the factors under 1000 (iirc). But these are easily reconstructed for example in Pari/GP shell or a one-off c+GMPlib (or perl+Math::BigInt) program. (Or you can fiddle with the guts of either gnfs-lasieve4e.c or msieve relation.c, again iirc, in order to print out all factors.)

2011-06-02, 20:39	#13
jasonp Tribal Bullet Oct 2004 3,541 Posts	Note that even a line sieve would have difficulty with 1024-bit GNFS; I tried with an older version of the current line sieve, and even with a factor base limit of 2^32 it only found three relations.

2011-06-07, 01:54	#14
Sleepy May 2011 23 Posts	I see.. I managed to get the sieving of RSA-768 to work on another PC. Thanks a lot for the help! =)

2011-06-10, 06:49	#15
Sleepy May 2011 23 Posts	Sorry another question, is it possible to remove the 308 digit limit to conduct some tests? i tried to edit some parts of the code but i think i am missing something crucial.

2011-06-10, 06:53	#16
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 3⁶×13 Posts	You need to increase the #define MAX_MP_WORDS 32 in mp.h to something bigger. The other places you probably already found.

2011-06-10, 08:07	#17
Sleepy May 2011 23 Posts	Hmm, i tried changing that to 34 or 40 but it still doesnt work. The error i got was: warning: NFS input not found in factor base file Any idea why i got that?

2011-06-10, 08:18	#18
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 3⁶·13 Posts	include/common.h:#define LINE_BUF_SIZE 300

2011-06-10, 09:16	#19
Sleepy May 2011 23 Posts	Thanks a lot!! I can run it now!! So that was the problem.. =D