Msieve 1.52 feedback - Page 3

ngoxuanhuy · 2014-05-14, 07:08

thanks a lot!!

WMHalsdorf · 2014-06-22, 00:53

Windows 32 bit - Msieve v. 1.52 (SVN 958)
Handles this 6^129-6^44-1
but dies on this 6^129-6^44+1

chris2be8 · 2015-02-21, 20:27

I've just had msieve 1.52 go into a loop in the square root stage:

Screen output was:

Code:

=>nice -n 19  "/home/chris/ggnfs/bin/msieve" -s e10_120-10_40-1.dat -l ggnfs.log -i e10_120-10_40-1.ini -v -nf e10_120-10_40-1.fb -t 1 -nc3


Msieve v. 1.52 (SVN 956)
Sat Feb 21 19:06:16 2015
random seeds: a251e42a e8dcb308
factoring 19231355861459592366670607793937564453051403742108983404068933029723859250293589710428697532893372557700853801 (110 digits)
searching for 15-digit factors
commencing number field sieve (110-digit input)
R0: -100000000000000000000
R1: 1
A0: -1
A1: 0
A2: -1
A3: 0
A4: 0
A5: 0
A6: 1
skew 1.00, size 3.702e-06, alpha 2.817, combined = 2.996e-09 rroots = 2

commencing square root phase
reading relations for dependency 1
read 54491 cycles
cycles contain 181760 unique relations
read 181760 relations
multiplying 181760 relations
multiply complete, coefficients have about 3.42 million bits
warning: no irreducible prime found, switching to small primes

received signal 15; shutting down

And the relevant part of the log was:

Code:

Sat Feb 21 19:06:16 2015 =>nice -n 19  "/home/chris/ggnfs/bin/msieve" -s e10_120-10_40-1.dat -l ggnfs.log -i e10_120-10_40-1.ini -v -nf e10_120-10_40-1.fb -t 1 -nc3
Sat Feb 21 19:06:16 2015
Sat Feb 21 19:06:16 2015
Sat Feb 21 19:06:16 2015  Msieve v. 1.52 (SVN 956)
Sat Feb 21 19:06:16 2015  random seeds: a251e42a e8dcb308
Sat Feb 21 19:06:16 2015  factoring 19231355861459592366670607793937564453051403742108983404068933029723859250293589710428697532893372557700853801 (110 digits)
Sat Feb 21 19:06:17 2015  searching for 15-digit factors
Sat Feb 21 19:06:17 2015  commencing number field sieve (110-digit input)
Sat Feb 21 19:06:17 2015  R0: -100000000000000000000
Sat Feb 21 19:06:17 2015  R1: 1
Sat Feb 21 19:06:17 2015  A0: -1
Sat Feb 21 19:06:17 2015  A1: 0
Sat Feb 21 19:06:17 2015  A2: -1
Sat Feb 21 19:06:17 2015  A3: 0
Sat Feb 21 19:06:17 2015  A4: 0
Sat Feb 21 19:06:17 2015  A5: 0
Sat Feb 21 19:06:17 2015  A6: 1
Sat Feb 21 19:06:17 2015  skew 1.00, size 3.702e-06, alpha 2.817, combined = 2.996e-09 rroots = 2
Sat Feb 21 19:06:17 2015
Sat Feb 21 19:06:17 2015  commencing square root phase
Sat Feb 21 19:06:17 2015  reading relations for dependency 1
Sat Feb 21 19:06:18 2015  read 54491 cycles
Sat Feb 21 19:06:18 2015  cycles contain 181760 unique relations
Sat Feb 21 19:06:20 2015  read 181760 relations
Sat Feb 21 19:06:20 2015  multiplying 181760 relations
Sat Feb 21 19:06:25 2015  multiply complete, coefficients have about 3.42 million bits
Sat Feb 21 19:06:25 2015  warning: no irreducible prime found, switching to small primes
Sat Feb 21 20:45:01 2015 -> Error - N is not fully factored, it's still 19231355861459592366670607793937564453051403742108983404068933029723859250293589710428697532893372557700853801!

The last message came from the script when I killed the msieve task. As you can see it was hung for over an hour.

In other factorizations the "warning: no irreducible prime found, switching to small primes" message was quickly followed by a "initial square root is modulo 53" message. Does this indicate where the error was?

I've still got all the files from the run in case you need them to debug the issue.

Chris

chris2be8 · 2015-03-13, 16:38

Here is the log from another case with a similar poly:

Code:

Thu Mar 12 20:07:39 2015 -> Working with NAME=e10_132_10_44-1...
(snip to start of -np3)
Thu Mar 12 22:36:21 2015 =>nice -n 19  "/home/chris/ggnfs/bin/msieve" -s e10_132_10_44-1.dat -l ggnfs.log -i e10_132_10_44-1.ini -v -nf e10 _132_10_44-1.fb -t 1 -nc3
Thu Mar 12 22:36:21 2015
Thu Mar 12 22:36:21 2015
Thu Mar 12 22:36:21 2015  Msieve v. 1.52 (SVN 956)
Thu Mar 12 22:36:21 2015  random seeds: 85f260e6 6f220bd7
Thu Mar 12 22:36:21 2015  factoring 1045183735662746890074241189290892705980070259932676928998742399474264810660159627938348943265703177350387663939 (112 digits)
Thu Mar 12 22:36:22 2015  searching for 15-digit factors
Thu Mar 12 22:36:23 2015  commencing number field sieve (112-digit input)
Thu Mar 12 22:36:23 2015  R0: -10000000000000000000000
Thu Mar 12 22:36:23 2015  R1: 1
Thu Mar 12 22:36:23 2015  A0: -1
Thu Mar 12 22:36:23 2015  A1: 0
Thu Mar 12 22:36:23 2015  A2: 1
Thu Mar 12 22:36:23 2015  A3: 0
Thu Mar 12 22:36:23 2015  A4: 0
Thu Mar 12 22:36:23 2015  A5: 0
Thu Mar 12 22:36:23 2015  A6: 1
Thu Mar 12 22:36:23 2015  skew 1.00, size 1.081e-06, alpha 2.641, combined = 1.476e-09 rroots = 2
Thu Mar 12 22:36:23 2015
Thu Mar 12 22:36:23 2015  commencing square root phase
Thu Mar 12 22:36:23 2015  reading relations for dependency 1
Thu Mar 12 22:36:23 2015  read 80592 cycles
Thu Mar 12 22:36:23 2015  cycles contain 267572 unique relations
Thu Mar 12 22:36:26 2015  read 267572 relations
Thu Mar 12 22:36:27 2015  multiplying 267572 relations
Thu Mar 12 22:36:35 2015  multiply complete, coefficients have about 5.12 million bits
Thu Mar 12 22:36:35 2015  warning: no irreducible prime found, switching to small primes
Thu Mar 12 22:55:06 2015  initial square root is modulo 59
Thu Mar 12 22:55:20 2015  Newton iteration failed to converge
Thu Mar 12 22:55:20 2015  algebraic square root failed
Thu Mar 12 22:55:20 2015  reading relations for dependency 2
Thu Mar 12 22:55:20 2015  read 80701 cycles
Thu Mar 12 22:55:20 2015  cycles contain 267576 unique relations
Thu Mar 12 22:55:23 2015  read 267576 relations
Thu Mar 12 22:55:24 2015  multiplying 267576 relations
Thu Mar 12 22:55:32 2015  multiply complete, coefficients have about 5.12 million bits
Fri Mar 13 01:51:43 2015  initial square root is modulo 59
Fri Mar 13 01:51:57 2015  Newton iteration failed to converge
Fri Mar 13 01:51:57 2015  algebraic square root failed
Fri Mar 13 01:51:57 2015  reading relations for dependency 3
Fri Mar 13 01:51:57 2015  read 80667 cycles
Fri Mar 13 01:51:57 2015  cycles contain 267642 unique relations
Fri Mar 13 01:52:00 2015  read 267642 relations
Fri Mar 13 01:52:01 2015  multiplying 267642 relations
Fri Mar 13 01:52:09 2015  multiply complete, coefficients have about 5.12 million bits
Fri Mar 13 01:52:09 2015  warning: no irreducible prime found, switching to small primes
Fri Mar 13 01:54:15 2015  initial square root is modulo 59
Fri Mar 13 01:54:29 2015  Newton iteration failed to converge
Fri Mar 13 01:54:29 2015  algebraic square root failed
Fri Mar 13 01:54:29 2015  reading relations for dependency 4
Fri Mar 13 01:54:29 2015  read 80743 cycles
Fri Mar 13 01:54:30 2015  cycles contain 267932 unique relations
Fri Mar 13 01:54:33 2015  read 267932 relations
Fri Mar 13 01:54:34 2015  multiplying 267932 relations
Fri Mar 13 01:54:41 2015  multiply complete, coefficients have about 5.12 million bits
Fri Mar 13 01:54:41 2015  warning: no irreducible prime found, switching to small primes
Fri Mar 13 04:22:11 2015  initial square root is modulo 59
Fri Mar 13 04:22:25 2015  Newton iteration failed to converge
Fri Mar 13 04:22:25 2015  algebraic square root failed
Fri Mar 13 04:22:25 2015  reading relations for dependency 5
Fri Mar 13 04:22:25 2015  read 80378 cycles
Fri Mar 13 04:22:26 2015  cycles contain 266882 unique relations
Fri Mar 13 04:22:29 2015  read 266882 relations
Fri Mar 13 04:22:30 2015  multiplying 266882 relations
Fri Mar 13 04:22:37 2015  multiply complete, coefficients have about 5.10 million bits
Fri Mar 13 04:22:37 2015  warning: no irreducible prime found, switching to small primes
Fri Mar 13 09:38:34 2015  initial square root is modulo 59
Fri Mar 13 09:38:48 2015  Newton iteration failed to converge
Fri Mar 13 09:38:48 2015  algebraic square root failed
Fri Mar 13 09:38:48 2015  reading relations for dependency 6
Fri Mar 13 09:38:48 2015  read 80981 cycles
Fri Mar 13 09:38:48 2015  cycles contain 268704 unique relations
Fri Mar 13 09:38:51 2015  read 268704 relations
Fri Mar 13 09:38:52 2015  multiplying 268704 relations
Fri Mar 13 09:38:59 2015  multiply complete, coefficients have about 5.14 million bits
Fri Mar 13 09:38:59 2015  warning: no irreducible prime found, switching to small primes
Fri Mar 13 11:35:45 2015  initial square root is modulo 59
Fri Mar 13 11:35:59 2015  GCD is 1, no factor found
Fri Mar 13 11:35:59 2015  reading relations for dependency 7
Fri Mar 13 11:35:59 2015  read 80410 cycles
Fri Mar 13 11:35:59 2015  cycles contain 267408 unique relations
Fri Mar 13 11:36:02 2015  read 267408 relations
Fri Mar 13 11:36:03 2015  multiplying 267408 relations
Fri Mar 13 11:36:10 2015  multiply complete, coefficients have about 5.11 million bits
Fri Mar 13 11:36:10 2015  warning: no irreducible prime found, switching to small primes
Fri Mar 13 15:54:44 2015  initial square root is modulo 59
Fri Mar 13 15:54:58 2015  Newton iteration failed to converge
Fri Mar 13 15:54:58 2015  algebraic square root failed
Fri Mar 13 15:54:58 2015  reading relations for dependency 8
Fri Mar 13 15:54:58 2015  read 80613 cycles
Fri Mar 13 15:54:58 2015  cycles contain 267994 unique relations
Fri Mar 13 15:55:01 2015  read 267994 relations
Fri Mar 13 15:55:02 2015  multiplying 267994 relations
Fri Mar 13 15:55:09 2015  multiply complete, coefficients have about 5.12 million bits
Fri Mar 13 15:55:09 2015  warning: no irreducible prime found, switching to small primes

It's still running!

Note that each dependency is taking as long as or longer than the sieving etc up to the start of -np3. Is there something special about this polynomial? And why does it take so long between "warning: no irreducible prime found, switching to small primes" and "initial square root is modulo 59"?

Chris

VBCurtis · 2015-03-13, 17:26

(deleted when I noticed my error)

henryzz · 2015-03-13, 18:11

Both polynomials are equal to (1+x+x^3)^2 in GF(2) if that makes any difference.

chris2be8 · 2015-03-14, 16:45

The second run finally finished. Here's the rest of the log:

Code:

Fri Mar 13 21:10:48 2015  initial square root is modulo 59
Fri Mar 13 21:11:02 2015  GCD is 1, no factor found
Fri Mar 13 21:11:02 2015  reading relations for dependency 9
Fri Mar 13 21:11:02 2015  read 80346 cycles
Fri Mar 13 21:11:02 2015  cycles contain 267190 unique relations
Fri Mar 13 21:11:05 2015  read 267190 relations
Fri Mar 13 21:11:06 2015  multiplying 267190 relations
Fri Mar 13 21:11:13 2015  multiply complete, coefficients have about 5.11 million bits
Fri Mar 13 21:11:13 2015  warning: no irreducible prime found, switching to small primes
Fri Mar 13 23:31:29 2015  initial square root is modulo 59
Fri Mar 13 23:31:43 2015  Newton iteration failed to converge
Fri Mar 13 23:31:43 2015  algebraic square root failed
Fri Mar 13 23:31:43 2015  reading relations for dependency 10
Fri Mar 13 23:31:43 2015  read 80807 cycles
Fri Mar 13 23:31:43 2015  cycles contain 268340 unique relations
Fri Mar 13 23:31:46 2015  read 268340 relations
Fri Mar 13 23:31:47 2015  multiplying 268340 relations
Fri Mar 13 23:31:54 2015  multiply complete, coefficients have about 5.13 million bits
Fri Mar 13 23:31:55 2015  warning: no irreducible prime found, switching to small primes
Sat Mar 14 03:36:21 2015  initial square root is modulo 59
Sat Mar 14 03:36:35 2015  Newton iteration failed to converge
Sat Mar 14 03:36:35 2015  algebraic square root failed
Sat Mar 14 03:36:35 2015  reading relations for dependency 11
Sat Mar 14 03:36:35 2015  read 80379 cycles
Sat Mar 14 03:36:35 2015  cycles contain 267290 unique relations
Sat Mar 14 03:36:38 2015  read 267290 relations
Sat Mar 14 03:36:39 2015  multiplying 267290 relations
Sat Mar 14 03:36:47 2015  multiply complete, coefficients have about 5.11 million bits
Sat Mar 14 03:36:47 2015  warning: no irreducible prime found, switching to small primes
Sat Mar 14 03:46:57 2015  initial square root is modulo 59
Sat Mar 14 03:47:11 2015  found factor: 213439243591039083385537792743511288853
Sat Mar 14 03:47:11 2015  reading relations for dependency 12
Sat Mar 14 03:47:11 2015  read 81055 cycles
Sat Mar 14 03:47:11 2015  cycles contain 268462 unique relations
Sat Mar 14 03:47:14 2015  read 268462 relations
Sat Mar 14 03:47:15 2015  multiplying 268462 relations
Sat Mar 14 03:47:22 2015  multiply complete, coefficients have about 5.13 million bits
Sat Mar 14 03:47:22 2015  warning: no irreducible prime found, switching to small primes
Sat Mar 14 04:08:50 2015  initial square root is modulo 59
Sat Mar 14 04:09:04 2015  sqrtTime: 106361
Sat Mar 14 04:09:04 2015  prp36 factor: 624957164401986995250622873971410107
Sat Mar 14 04:09:04 2015  prp37 factor: 7835525326639299785500312383143883509
Sat Mar 14 04:09:04 2015  prp39 factor: 213439243591039083385537792743511288853
Sat Mar 14 04:09:04 2015  elapsed time 29:32:43

I know the poly could be written as degree 3, but I wrote it as degree 6 because 3 is too small for this size of job.

Could someone who know C look at this code from msieve-svn/trunk/gnfs/sqrt/sqrt_a.c and say what it could be doing for hours between the "switching to small primes" message and the "initial square root is modulo %u\n" message?

Code:

       for (i = 0; i < ISQRT_NUM_ATTEMPTS; i++) {
                if (get_prime_for_sqrt(alg_poly, start_q + 1, &q)) {
                        if (start_q > 150) {
                                logprintf(obj, "warning: no irreducible prime "
                                        "found, switching to small primes\n");
                                start_q = 50;
                                /* for octics, even mod 13 works and
                                   is resonably fast */
                                if (alg_poly->degree > 6)
                                        start_q = 12;
                                continue;
                        }
                }

                /* find the reciprocal square root mod q, or try
                   another q if this fails */

                if (inv_sqrt_mod_q(isqrt_mod_q, prod,
                                alg_poly, q, &obj->seed1, &obj->seed2)) {
                        break;
                }
                start_q = q;
        }

        alg_poly->degree--;

        if (i == ISQRT_NUM_ATTEMPTS) {
                logprintf(obj, "error: cannot recover square root mod q\n");
                return 0;
        }

        logprintf(obj, "initial square root is modulo %u\n", q);
        mpz_set_ui(q_out, (unsigned long)q);
        return 1;

Chris

jasonp · 2015-03-14, 17:36

The algebraic square root depends on finding a small prime p so that (algebraic polynomial) modulo p is irreducible. If such a p exists then you can always find a square root of any element in the number field modulo p.

There are some polynomials for which no such p exists; most are degree 4 and a very few (like this one) are degree 6. It's still possible to find that square root even though (algebraic polynomial) modulo p is reducible, but there's no fast algorithm for finding the square root. So the code picks a small p and for algebraic polynomial of degree d it tries all p^d polynomials looking for one that is the square root. I guess there's something pathological about this polynomial where the square root doesn't even exist for most p, so that larger and larger p have to be tried.

Either that or there's a bug in that code that makes it fail when it should not :) Most times the brute force method still finishes almost instantly. It doesn't help that this number has 3 factors, so that at least two dependencies have to succeed before the factorization can complete.

chris2be8 · 2015-03-15, 17:10

Quote:

Originally Posted by jasonp

So the code picks a small p and for algebraic polynomial of degree d it tries all p^d polynomials looking for one that is the square root.

Could have tried a huge number of polynomials for p=53, none of which worked, before switching to p=59? That would explain the delay of several hours between the messages.

If it had found one factor while I was watching it I would have killed msieve and finished the job with QS.

If I meet another number like this I'll try degree 3. The sieving will probably be slower, but the square root should work normally.

Chris

PS. Is there an option to tell msieve which small prime to try first? It could be useful if every relation failed to find a factor as well as in this case.

Another option would be for msieve to start with the small prime that worked for the previous relation.

chris2be8 · 2015-04-18, 15:49

Here is the log for another poly where the square root stage is very slow:

Code:

Sat Apr 18 06:55:55 2015  Msieve v. 1.52 (SVN 956)
Sat Apr 18 06:55:55 2015  random seeds: 15952e44 e9496df8
Sat Apr 18 06:55:55 2015  factoring 264686027910580146415939546152481861543809933994772164588381408052029553257836677596270482607867310525329 (105 digits)
Sat Apr 18 06:55:56 2015  no P-1/P+1/ECM available, skipping
Sat Apr 18 06:55:56 2015  commencing number field sieve (105-digit input)
Sat Apr 18 06:55:56 2015  R0: -576460752303423488
Sat Apr 18 06:55:56 2015  R1: 1
Sat Apr 18 06:55:56 2015  A0: -1
Sat Apr 18 06:55:56 2015  A1: 0
Sat Apr 18 06:55:56 2015  A2: 0
Sat Apr 18 06:55:56 2015  A3: 0
Sat Apr 18 06:55:56 2015  A4: -2
Sat Apr 18 06:55:56 2015  A5: 0
Sat Apr 18 06:55:56 2015  A6: 1024
Sat Apr 18 06:55:56 2015  skew 0.31, size 1.245e-05, alpha -0.227, combined = 5.856e-09 rroots = 2
Sat Apr 18 06:55:56 2015
Sat Apr 18 06:55:56 2015  commencing square root phase
Sat Apr 18 06:55:56 2015  reading relations for dependency 1
Sat Apr 18 06:55:56 2015  read 38495 cycles
Sat Apr 18 06:55:56 2015  cycles contain 139138 unique relations
Sat Apr 18 06:56:04 2015  read 139138 relations
Sat Apr 18 06:56:05 2015  multiplying 139138 relations
Sat Apr 18 06:56:23 2015  multiply complete, coefficients have about 3.74 million bits
Sat Apr 18 06:56:24 2015  warning: no irreducible prime found, switching to small primes
Sat Apr 18 09:09:24 2015  initial square root is modulo 53
Sat Apr 18 09:10:18 2015  Newton iteration failed to converge
Sat Apr 18 09:10:18 2015  algebraic square root failed
Sat Apr 18 09:10:18 2015  reading relations for dependency 2
Sat Apr 18 09:10:18 2015  read 38705 cycles
Sat Apr 18 09:10:18 2015  cycles contain 140124 unique relations
Sat Apr 18 09:10:26 2015  read 140124 relations
Sat Apr 18 09:10:27 2015  multiplying 140124 relations
Sat Apr 18 09:10:45 2015  multiply complete, coefficients have about 3.76 million bits
Sat Apr 18 09:10:46 2015  warning: no irreducible prime found, switching to small primes
Sat Apr 18 11:40:03 2015  initial square root is modulo 53
Sat Apr 18 11:40:58 2015  Newton iteration failed to converge
Sat Apr 18 11:40:58 2015  algebraic square root failed
Sat Apr 18 11:40:58 2015  reading relations for dependency 3
Sat Apr 18 11:40:58 2015  read 38696 cycles
Sat Apr 18 11:40:58 2015  cycles contain 139444 unique relations
Sat Apr 18 11:41:06 2015  read 139444 relations
Sat Apr 18 11:41:07 2015  multiplying 139444 relations
Sat Apr 18 11:41:25 2015  multiply complete, coefficients have about 3.74 million bits
Sat Apr 18 11:41:25 2015  warning: no irreducible prime found, switching to small primes
Sat Apr 18 12:47:09 2015  initial square root is modulo 53
Sat Apr 18 12:48:03 2015  Newton iteration failed to converge
Sat Apr 18 12:48:03 2015  algebraic square root failed
Sat Apr 18 12:48:03 2015  reading relations for dependency 4
Sat Apr 18 12:48:03 2015  read 38604 cycles
Sat Apr 18 12:48:03 2015  cycles contain 139338 unique relations
Sat Apr 18 12:48:11 2015  read 139338 relations
Sat Apr 18 12:48:12 2015  multiplying 139338 relations
Sat Apr 18 12:48:30 2015  multiply complete, coefficients have about 3.74 million bits
Sat Apr 18 12:48:30 2015  warning: no irreducible prime found, switching to small primes
Sat Apr 18 13:43:03 2015  initial square root is modulo 53
Sat Apr 18 13:43:58 2015  sqrtTime: 24482
Sat Apr 18 13:43:58 2015  prp42 factor: 102704350031757510232163958262187668675847
Sat Apr 18 13:43:58 2015  prp64 factor: 2577164724071919167213984305886524197809188758868886880716375207
Sat Apr 18 13:43:58 2015  elapsed time 06:48:03

I assume it's another variation on the same issue.

Does anyone know why these particular polys do this?

Chris

Batalov · 2015-04-18, 20:15

There are five factors for 2^364-2^237-1 which you were factoring.
If thre was some tricky Aurif.-like factorization, you could see it in log(2), but nothing springs out:

Code:

(13:10) gp > for(i=1,31,m=prod(k=1,#v,v[k]^bittest(i,k-1));print(i" "log(m)/log(2)))
1 2.807354922057604107441969317
2 4.087462841250339408254066011
3 6.894817763307943515696035328
4 10.22037832769522802943431729
5 13.02773324975283213687628661
6 14.30784116894556743768838330
7 17.11519609100317154513035262
8 136.2375491785261592954147370
9 139.0449041005837634028567063
10 140.3250120197764987036688030
11 143.1323669418341028111107723
12 146.4579275062213873248490543
13 149.2652824282789914322910236
14 150.5453903474717267331031203
15 153.3527452695293308405450896
16 210.6472547304706691594549104
17 213.4546096525282732668968797
18 214.7347175717210085677089764
19 217.5420724937786126751509457
20 220.8676330581658971888892277
21 223.6749879802235012963311970
22 224.9550958994162365971432937
23 227.7624508214738407045852630
24 346.8848039089968284548696474
25 349.6921588310544325623116167
26 350.9722667502471678631237134
27 353.7796216723047719705656827
28 357.1051822366920564843039647
29 359.9125371587496605917459340
30 361.1926450779423958925580307
31 364.0000000000000000000000000

Just a special polynomial. Jason may shed some light.

And yes, brute-force square root mod small primes is sort of slow and capricious. But it works.

2015-03-13, 17:26	#27
VBCurtis "Curtis" Feb 2005 Riverside, CA 4,861 Posts	(deleted when I noticed my error) Last fiddled with by VBCurtis on 2015-03-13 at 17:26

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Msieve 1.53 feedback	xilman	Msieve	149	2018-11-12 06:37
Msieve 1.50 feedback	firejuggler	Msieve	99	2013-02-17 11:53
Msieve 1.43 feedback	Jeff Gilchrist	Msieve	47	2009-11-24 15:53
Msieve 1.42 feedback	Andi47	Msieve	167	2009-10-18 19:37
Msieve 1.41 Feedback	Batalov	Msieve	130	2009-06-09 16:01

2014-05-14, 07:08	#23
ngoxuanhuy May 2014 3₈ Posts	thanks a lot!!

2014-06-22, 00:53	#24
WMHalsdorf Feb 2005 Bristol, CT 3³×19 Posts	Windows 32 bit - Msieve v. 1.52 (SVN 958) Handles this 6^129-6^44-1 but dies on this 6^129-6^44+1

2015-03-13, 18:11	#28
henryzz Just call me Henry "David" Sep 2007 Cambridge (GMT/BST) 1011011111000₂ Posts	Both polynomials are equal to (1+x+x^3)^2 in GF(2) if that makes any difference.

2015-03-14, 17:36	#30
jasonp Tribal Bullet Oct 2004 3,541 Posts	The algebraic square root depends on finding a small prime p so that (algebraic polynomial) modulo p is irreducible. If such a p exists then you can always find a square root of any element in the number field modulo p. There are some polynomials for which no such p exists; most are degree 4 and a very few (like this one) are degree 6. It's still possible to find that square root even though (algebraic polynomial) modulo p is reducible, but there's no fast algorithm for finding the square root. So the code picks a small p and for algebraic polynomial of degree d it tries all p^d polynomials looking for one that is the square root. I guess there's something pathological about this polynomial where the square root doesn't even exist for most p, so that larger and larger p have to be tried. Either that or there's a bug in that code that makes it fail when it should not :) Most times the brute force method still finishes almost instantly. It doesn't help that this number has 3 factors, so that at least two dependencies have to succeed before the factorization can complete.