mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2006-06-13, 23:51   #1
fetofs
 
fetofs's Avatar
 
Aug 2005
Brazil

2·181 Posts
Default SNFS trivial factorization

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?
fetofs is offline   Reply With Quote
Old 2006-06-14, 01:13   #2
Wacky
 
Wacky's Avatar
 
Jun 2003
The Texas Hill Country

32·112 Posts
Default

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.
Wacky is offline   Reply With Quote
Old 2006-06-14, 01:30   #3
fetofs
 
fetofs's Avatar
 
Aug 2005
Brazil

5528 Posts
Default

Quote:
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...

Last fiddled with by fetofs on 2006-06-14 at 01:30
fetofs is offline   Reply With Quote
Old 2006-06-14, 06:09   #4
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

9A316 Posts
Default

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

Last fiddled with by akruppa on 2006-06-14 at 07:43
akruppa is offline   Reply With Quote
Old 2006-06-14, 06:53   #5
ValerieVonck
 
ValerieVonck's Avatar
 
Mar 2004
Belgium

839 Posts
Default

Quote:
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

Last fiddled with by ValerieVonck on 2006-06-14 at 06:55
ValerieVonck is offline   Reply With Quote
Old 2006-06-14, 09:37   #6
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

1D2416 Posts
Default

Quote:
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.
R.D. Silverman is offline   Reply With Quote
Old 2006-06-14, 11:46   #7
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

3·3,529 Posts
Default

Quote:
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
xilman is offline   Reply With Quote
Old 2006-06-14, 13:06   #8
fetofs
 
fetofs's Avatar
 
Aug 2005
Brazil

2·181 Posts
Default

Quote:
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?
fetofs is offline   Reply With Quote
Old 2006-06-14, 13:23   #9
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

46438 Posts
Default

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 N1/p is below your trial division limit.

Alex
akruppa is offline   Reply With Quote
Old 2006-06-14, 14:00   #10
fetofs
 
fetofs's Avatar
 
Aug 2005
Brazil

36210 Posts
Default

Quote:
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 N1/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?
fetofs is offline   Reply With Quote
Old 2006-06-14, 14:25   #11
smh
 
smh's Avatar
 
"Sander"
Oct 2002
52.345322,5.52471

29·41 Posts
Default

Dump some relations and sieve a bit further before rebuilding the matrix again.
smh is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Suddenly I'm getting only trivial TF tests fivemack Software 34 2015-10-25 16:54
Weird issue with resuming after trivial NFS factorization pakaran YAFU 8 2015-09-09 15:57
Trivial question davieddy Information & Answers 6 2011-12-08 08:07
Trivial bug: repeated PM notifications Christenson Forum Feedback 0 2011-03-21 03:49
"Trivial" factorization algorithms Fusion_power Math 13 2004-12-28 20:46

All times are UTC. The time now is 01:59.

Sat Feb 27 01:59:11 UTC 2021 up 85 days, 22:10, 1 user, load averages: 1.97, 1.63, 1.74

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.