Register FAQ Search Today's Posts Mark Forums Read

2007-03-06, 19:08   #12
ewmayer
2ω=0

Sep 2002
República de California

22×5×11×53 Posts

Quote:
 Originally Posted by akruppa 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.

2007-03-10, 08:40   #13
frmky

Jul 2003
So Cal

89116 Posts

Quote:
 Originally Posted by xilman 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. Paul
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.

Greg

 2007-04-13, 23:26 #14 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 144518 Posts Different wall Can you see the problem with this code: Code: PREFIX=parsed rm $PFX* for i in *.rels; do /home/fivemack/maths/ggnfs-0.77.1/ggnfs/bin/procrels -fb foo.fb -prel$PREFIX -newrels $i; done Fortunately, text forms of relations are fairly easy to see in a disc image Code: for i in seq 0 218; do 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; done 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 Code: [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

 Similar Threads Thread Thread Starter Forum Replies Last Post Gandolf Math 49 2017-04-13 20:00 ixfd64 Lounge 24 2012-08-20 21:00 Prime Monster Lounge 23 2012-02-11 11:08 wblipp Lounge 27 2010-09-18 13:03 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