SNFS trivial factorization

[fetofs]

Hi guys! I'm factoring a number using SNFS, and for all dependencies, it returned the result:

From dependence x, sqrt obtained:
r1=1

Is this possible or does it reveal some bugs in the ggnfs software I'm using? Can I complete the factorization without having to start sieving all over again?

[Wacky]

Assuming that the "problem" is actually that you found only trivial factorizations (as opposed to some "bug" in either your hardware, software, or parameters), you can always do some additional sieving and add the new relations to the previous set.

However, before I would be willing to say anything more, I would need a lot more details in order to make an educated guess as to what went wrong.

[fetofs]

Originally Posted by Wacky

Assuming that the "problem" is actually that you found only trivial factorizations (as opposed to some "bug" in either your hardware, software, or parameters), you can always do some additional sieving and add the new relations to the previous set.

I'll try a little more of sieving, then...

[akruppa]

How many different dependencies were there? The odds of getting only trivial factorisatons in n dependencies is 2^-[I]n[/I] (assuming 2 prime factors in your number). If you only had maybe five or six dependencies, it might have been simple bad luck. If you had twenty and they all failed to find a proper factor, I'd invesitagte for possible software problems before spending more time sieving.

Alex

[ValerieVonck]

Originally Posted by akruppa

How many different dependencies were there? The odds of getting only trivial factorisatons in n dependencies is 2^-[I]n[/I] (assuming 2 prime factors in you number). If you only had maybe five or six dependencies, it might have been simple bad luck. If you had twenty and they all failed to find a proper factor, I'd invesitagte for possible software problems before spending more time sieveing.

Alex

Hi Alex

A time ago, when I did a C130+ digit SNFS factorization, I also had the problem that the GGNFS Suite (0.77.1 snapshot 200509...) returned a trivial factor of r1=1 for each of the 32 dependencies.

After that, I factored other number successfully with SNFS & GNFS, all be it with number much smaller (C87 => C115).

BTW, I use the factLat.pl script

Regards
Cedric

[R.D. Silverman]

Originally Posted by CedricVonck

Hi Alex

A time ago, when I did a C130+ digit SNFS factorization, I also had the problem that the GGNFS Suite (0.77.1 snapshot 200509...) returned a trivial factor of r1=1 for each of the 32 dependencies.

After that, I factored other number successfully with SNFS & GNFS, all be it with number much smaller (C87 => C115).

BTW, I use the factLat.pl script

Regards
Cedric

Two possible problems:

(1) Duplicate relations
(2) The number being factored was actually prime.

[xilman]

Originally Posted by R.D. Silverman

Two possible problems:

(1) Duplicate relations
(2) The number being factored was actually prime.

I think you meant to say:
(2) The number being factored was actually a prime power.

Paul

[fetofs]

Originally Posted by akruppa

If you had twenty and they all failed to find a proper factor, I'd invesitagte for possible software problems before spending more time sieving.

Alex

Just like Cedric said, there were 32...
I thought that might be a bit strange, that's why I posted this...
Is there any way to check if my number is a prime power?

[akruppa]

First of all test if it is a prime. Technically, NFS will fail for prime powers as well, but the chance that a large number is a prime power but no prime and without small factors is really slim. If you want to test for prime powers as well, you could try if the square root, cube root, fifth root, generally: the p-th root (p prime) are integers, until N^1/p is below your trial division limit.

Alex

[fetofs]

Originally Posted by akruppa

First of all test if it is a prime. Technically, NFS will fail for prime powers as well, but the chance that a large number is a prime power but no prime and without small factors is really slim. If you want to test for prime powers as well, you could try if the square root, cube root, fifth root, generally: the p-th root (p prime) are integers, until N^1/p is below your trial division limit.

Alex

Well, I'm sure that it isn't a prime, and it isn't a power (I've verified that with GMPy just now), so should I go for more sieving or question the developer?

[smh]

Dump some relations and sieve a bit further before rebuilding the matrix again.