Go Back > Factoring Projects > Factoring

Thread Tools
Old 2007-03-06, 19:08   #12
ewmayer's Avatar
Sep 2002
Rep├║blica de California

22×5×11×53 Posts

Originally Posted by akruppa View Post
the problem is that with large input numbers that are to be tried with low B1 values, doing a PRP test first will take several times the time of the P-1/ECM/whatever attempt. We'd need some threshold for which numbers get a PRP test and which ones don't.
Actually, in thinking about this a bit more, it's probably most needed for GNFS, since ECM and SNFS often use (or in the latter case, need) composite inputs.

Maybe just tweak the code to check inputs below a certain size (1000-10000 digts sounds like roughly the right range) via prp test and issue a "composite" warning if the input is found to be so via prp.
ewmayer is offline   Reply With Quote
Old 2007-03-10, 08:40   #13
frmky's Avatar
Jul 2003
So Cal

89116 Posts

Originally Posted by xilman View Post
As I suggested earlier, a test for a prime power would be a very good idea for any utility which attempts to find non-trivial solutions to x^2-y^2 == 0 mod N. Such algorithms include QS and NFS.

I just added prime and perfect power tests to the input number just before the factor base is created in GGNFS. I don't have access to upload a source snapshot, so you'll have to grab the latest CVS source to get the changes.

frmky is offline   Reply With Quote
Old 2007-04-13, 23:26   #14
(loop (#_fork))
fivemack's Avatar
Feb 2006
Cambridge, England

144518 Posts
Default Different wall

Can you see the problem with this code:
rm $PFX*
for i in *.rels; 
do /home/fivemack/maths/ggnfs-0.77.1/ggnfs/bin/procrels -fb foo.fb -prel $PREFIX -newrels $i;

Fortunately, text forms of relations are fairly easy to see in a disc image
for i in `seq 0 218`;
    dd if=/dev/sdb2 of=block$i bs=1G skip=$i;
    strings -n 40 block$i | grep '^[-0-9,]*:[0-9a-fA-F:,]*$') > rels$i;
and I've just demonstrated that you can in practice recover Y1, Y0 and c0 through c5 from any six relations ... the only issue is that you've lost the sign of the algebraic norm f(x), so have to solve the matrix equation

[a1^5 a1^4b1 a1^3b1^2 a1^2b1^3 a1b1^4 b1^5]  [c5] = [+/- algnorm1]
[a2^5 a2^4b2 a2^3b2^2 a2^2b2^3 a2b2^4 b2^5]  [c4]    [+/- algnorm2]
[a3^5 a3^4b3 a3^3b3^2 a3^2b3^3 a3b3^4 b3^5]  [c3]    [+/- algnorm3]
after putting all 64 choices of sign on the algnorms. Only one set of signs gives you integer coefficients of reasonable size.

Once you know Y1 and Y0, a little Python script can go through the rather large (for there were relations from many factorisations on the disc) set of strings of the right form, and check that the factorisation of the algebraic side is right; then you get a couple of gigabytes of text to feed to procrels, and hopefully happiness ensues.

Disc space is cheap and human folly common, there's no need ever to have 'rm' in a relation-processing script

Last fiddled with by fivemack on 2007-04-13 at 23:31
fivemack is online now   Reply With Quote

Thread Tools

Similar Threads
Thread Thread Starter Forum Replies Last Post
Wall-Sun-Sun primes Gandolf Math 49 2017-04-13 20:00
If you could meet any Mersenne prime discoverer... ixfd64 Lounge 24 2012-08-20 21:00
The Hello - I am - Nice to meet you thread.... Prime Monster Lounge 23 2012-02-11 11:08
Meet the English? wblipp Lounge 27 2010-09-18 13:03
The Ladder Against The Wall Numbers Puzzles 27 2005-07-02 10:19

All times are UTC. The time now is 19:55.

Sat Oct 23 19:55:00 UTC 2021 up 92 days, 14:23, 0 users, load averages: 0.92, 0.92, 1.08

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.