Error message when factoring

[hulpke]

From an example reported on the support list:

gap> Factors(998582188058818939);
Error, no method found! For debugging hints type ?Recovery from NoMethodFound
Error, no 1st choice method found for `[]' on 2 arguments at /Users/hulpke/gap4/lib/methsel2.g:249 called from
while aFactorsSelectedPositions[i] = aFactorsPoolsize - (NraFactors - i) do
    i := i - 1;
od; at /Users/hulpke/gap4/pkg/FactInt/lib/mpqs.gi:250 called from
MPQSSplit( FactorsList[Pos] ) at /Users/hulpke/gap4/pkg/FactInt/lib/mpqs.gi:533 called from
CallFuncList( FactoringMethod, Arguments
 ) at /Users/hulpke/gap4/pkg/FactInt/lib/general.gi:363 called from
ApplyFactoringMethod( FactorsMPQS, [  ], FactorizationObtainedSoFar,
 MPQSBound, [ "Multiple Polynomial Quadratic Sieve (MPQS)\n",
    "Number to be factored : ", "n" ]
 ); at /Users/hulpke/gap4/pkg/FactInt/lib/general.gi:1015 called from
FactInt( n ) at /Users/hulpke/gap4/pkg/FactInt/lib/general.gi:1102 called from
...  at *stdin*:7
type 'quit;' to quit to outer loop
brk> i;
2
brk> Length(aFactorsSelectedPositions);
1

[olexandr-konovalov]

Thanks, this is reproducible:

gap> Factors(998582188058818939);
Error, no method found! For debugging hints type ?Recovery from NoMethodFound
Error, no 1st choice method found for `[]' on 2 arguments at /Users/alexk/gap/gap-4.11.1/lib/methsel2.g:249 called from
while aFactorsSelectedPositions[i] = aFactorsPoolsize - (NraFactors - i) do
    i := i - 1;
od; at /Users/alexk/gap/gap-4.11.1/pkg/FactInt-1.6.3/lib/mpqs.gi:250 called from
MPQSSplit( FactorsList[Pos] ) at /Users/alexk/gap/gap-4.11.1/pkg/FactInt-1.6.3/lib/mpqs.gi:542 called from
CallFuncList( FactoringMethod, Arguments ) at /Users/alexk/gap/gap-4.11.1/pkg/FactInt-1.6.3/lib/general.gi:321 called from
ApplyFactoringMethod( FactorsMPQS, [  ], FactorizationObtainedSoFar, MPQSBound, 
 [ "Multiple Polynomial Quadratic Sieve (MPQS)\n", "Number to be factored : ", "n" ] 
 ); at /Users/alexk/gap/gap-4.11.1/pkg/FactInt-1.6.3/lib/general.gi:974 called from
FactInt( N ) at /Users/alexk/gap/gap-4.11.1/pkg/FactInt-1.6.3/lib/general.gi:1061 called from
...  at *stdin*:1
type 'quit;' to quit to outer loop
brk> ShowArguments();
[ [ 18 ], 0 ]
brk> i;
2
brk> aFactorsSelectedPositions;
[ 18 ]

in several versions:

• GAP 4.11.1 with FactInt 1.6.3
• GAP 4.10.2 with FactInt 1.6.2
• GAP 4.9.3 with FactInt 1.6.2

[olexandr-konovalov]

A bit more details:

• git blame reports the code around FactInt-1.6.3/lib/mpqs.gi:250 last changes by @Stefan-Kohl in 2001

• with higher IntegerFactorizationInfo level, I observe this

gap> Factors(998582188058818939);
#I  
#I  Check for n = b^k +/- 1
#I  
#I  Factors already found : [  ]
#I  
#I  
#I  Trial division by all primes p < 1000
#I  
#I  Trial division by some cached factors
#I  
#I  Check for perfect powers
#I  
#I  Fermat's method
#I  
#I  Pollard's Rho
Steps = 16384, Cluster = 34
Number to be factored : 998582188058818939
#I  
#I  Multiple Polynomial Quadratic Sieve (MPQS)
Number to be factored : 998582188058818939
#I  Pass no. 1
#I  MPQS for n = 998582188058818939
#I  Digits                     :         18
#I  Multiplier                 :          3
#I  Size of factor base        :         58
#I  Factor base : 
[ -1, 2, 3, 11, 13, 23, 53, 67, 71, 73, 103, 107, 139, 181, 199, 211, 233, 239, 241, 251, 263, 271, 277, 281, 293, 311, 313, 317, 337, 359, 389, 401, 439, 
  457, 461, 467, 491, 541, 547, 577, 593, 601, 607, 613, 617, 631, 641, 653, 659, 661, 677, 709, 727, 757, 769, 787, 797, 809 ]

#I  Prime powers to be sieved  :         64
#I  Length of sieving interval :       2048
#I  Small prime limit          :          9
#I  Large prime limit          :      23010
#I  Number of used a-factors   :          1
#I  Size of a-factors pool     :         18
#I  a-factors pool :
[ 2390077, 2390099, 2390111, 2390117, 2390123, 2390197, 2390221, 2390243, 2390299, 2390417, 2390431, 2390449, 2390473, 2390477, 2390519, 2390579, 2390623, 
  2390711 ]

#I  Initialization time        :          0 sec.
#I  
#I  Sieving
#I  
#I  Collecting relations with a large factor
#I  Complete factorizations over the factor base   :       14
#I  Relations with a large prime factor            :        4
#I  Relations remaining to be found                :       78
#I  Total factorizations with a large prime factor :       71
#I  Used polynomials                               :        4
#I  Efficiency 1                                   :       73 %
#I  Efficiency 2                                   :       59 %
#I  Elapsed runtime                                :        0 sec.
#I  Progress (relations)                           :       18 %
#I  
#I  
#I  Collecting relations with a large factor
#I  Complete factorizations over the factor base   :       20
#I  Relations with a large prime factor            :       12
#I  Relations remaining to be found                :       64
#I  Total factorizations with a large prime factor :      134
#I  Used polynomials                               :        7
#I  Efficiency 1                                   :       76 %
#I  Efficiency 2                                   :       58 %
#I  Elapsed runtime                                :        0 sec.
#I  Progress (relations)                           :       33 %
#I  
#I  
#I  Collecting relations with a large factor
#I  Complete factorizations over the factor base   :       31
#I  Relations with a large prime factor            :       40
#I  Relations remaining to be found                :       25
#I  Total factorizations with a large prime factor :      248
#I  Used polynomials                               :       13
#I  Efficiency 1                                   :       76 %
#I  Efficiency 2                                   :       56 %
#I  Elapsed runtime                                :        0 sec.
#I  Progress (relations)                           :       73 %
#I  
#I  
#I  Collecting relations with a large factor
#I  Complete factorizations over the factor base   :       41
#I  Relations with a large prime factor            :       49
#I  Relations remaining to be found                :        6
#I  Total factorizations with a large prime factor :      280
#I  Used polynomials                               :       15
#I  Efficiency 1                                   :       76 %
#I  Efficiency 2                                   :       57 %
#I  Elapsed runtime                                :        0 sec.
#I  Progress (relations)                           :       93 %
#I  
Error, no method found! For debugging hints type ?Recovery from NoMethodFound
Error, no 1st choice method found for `[]' on 2 arguments at /Users/alexk/gap/gap-4.11.1/lib/methsel2.g:249 called from
while aFactorsSelectedPositions[i] = aFactorsPoolsize - (NraFactors - i) do
    i := i - 1;
od; at /Users/alexk/gap/gap-4.11.1/pkg/FactInt-1.6.3/lib/mpqs.gi:250 called from
MPQSSplit( FactorsList[Pos] ) at /Users/alexk/gap/gap-4.11.1/pkg/FactInt-1.6.3/lib/mpqs.gi:542 called from
CallFuncList( FactoringMethod, Arguments ) at /Users/alexk/gap/gap-4.11.1/pkg/FactInt-1.6.3/lib/general.gi:321 called from
ApplyFactoringMethod( FactorsMPQS, [  ], FactorizationObtainedSoFar, MPQSBound, [ "Multiple Polynomial Quadratic Sieve (MPQS)\n", 
    "Number to be factored : ", "n" ] ); at /Users/alexk/gap/gap-4.11.1/pkg/FactInt-1.6.3/lib/general.gi:974 called from
FactInt( N ) at /Users/alexk/gap/gap-4.11.1/pkg/FactInt-1.6.3/lib/general.gi:1061 called from
...  at *stdin*:2
type 'quit;' to quit to outer loop
brk> 

[fingolfin]

I wonder if @Stefan-Kohl has any idea about resolving this FactInt bug?

[Stefan-Kohl]

@fingolfin I just noticed this old unresolved issue. I fixed the bug in one of many possible ways (if the MPQS runs out of polynomials, use CFRAC instead). That case should likely occur only for relatively "small" numbers of around 20 digits, but due to the probabilistic nature of the method, one cannot be completely sure about that.