[top] [TitleIndex] [WordIndex]

# ant07/projects/shumow raw

## Shumow -- GNFS -- raw notebook code

To use this in Sage, click edit in this page and edit in a sage worksheet and copy the resulting plain text into the sage worksheet.

GNFS Term Project system:sage

```id=0|
#
# This is a Toy implementation of the General Number Field Sieve For Factoring
#
# Author:
#
# Math 581F Fall 2007
# Professor William Stein
# Final Project
#
# "You haven't lived till you've sieved."
#

#  The following are the sources I used to learn about the General Number Field Sieve

#  Matthew E Briggs Master's Thesis from Virginia Polytech (This is probably the most clear and detailed)
#  The Lenstra et al book "The development of the number field sieve"
#  Pomerance's "Tale of Two Sieves"
#  Henri Cohn's "A Course in Computational Algebraic Number Theory"
#  The Math 581F Textbook / Lecture Notes (William Stein)
#
#  Personal conversations with Peter Montgomery
```

```id=61|
#
# The General Number Field Sieve works like this
#
# 1) Decide to use GNFS to factor N, determine algorithm parameters based on N
#    such as, the size of the rational factor base, size of the algebraic factor base
#    number of quadratic characters, degree d, and polynomial f to use
#
# 2) calculate the rational prime factor base (primes up to bound)
# 3) calculate the algebraic factor base (first degree prime ideals up to bound)
# 4) calculate the quadratic characters (first few 1st degree prime ideals beyond the algebraic factor base.)
# 5) use sieving to determine integer pairs (a,b) that have values
#    have a+b*m (m a root of f mod N) and N(a+b*theta) (theta complex root of f)
#    smooth with respect to both the algebraic and rational prime factor bases.
#    while sieving, also determine the degree mod 2 over each prime (rational and algebraic)
#    and save this information.
#    Also, record the power (mod 2) of -1 determining the legendre symbol (a+b*s / q) of the
#    first degree prime ideal (s,q) in the quadratic character base.
# 6) Once there are enough such primes more than the sum of the lengths of the bases
#    use linear algebra to determine the kernel of the transformation.
# 7) Use the result of step 6 to calculate a product of (a+b*theta)'s =  Beta^2 in the number field
# 8) Use the CRT to determine Beta from Beta^2 in the number field
# 9) replace theta in Beta^2 with m to obtain v^2 = phi(m)
# 10) calculate u^2 = product of (a+b*m)'s mod N, calculate u from (a+b*m)
# 11) u^2 - v^2 = 0 mod N, so use difference of squares trick to try to factor N.
# 12) repeat until N is factored.
#
```

```id=67|
#
# Major Weaknesses of this project:
# The major weaknesses of this project are that I relied a lot on sage
# to do math.  Although it served its purpose in teaching me about the GNFS.
#
# WARNING!!!
# On My Laptop This Notebook can not handle in the mid to high 8 digits.
#
# Other than that:
# 1) To calculate square roots, I should use the CRT, but instead
#    I let sage functions do the work for me.
#    I did this because, the CRT is a technical detail at the end of the
#    algorithm, and also, I understand that math already.
#    I wanted to focus on learning the stuff I didn't understand.
# 2) I rely on sage for all linear algebra, this wouldn't work at limits where
#    10s or 100s of thousands of elements may be in the factor base.
# 3) This program uses is_prime_power() to try and determine if an N is a prime power
#    (because the GNFS does not work well on prime powers.)
#    This function is actually the limit on sizes of N that can be factored.
# 4) If a number is a prime power, I use the ECM to factor it, in actuality
#    an algorithm would be selected heuristically.
#
```

```id=62|
#
# Global Flags: These can be set to change the behavior of the sieving algorithm
# Used for sort of anecdotal observation and experimentation of the algorithm
#

# if this value is set to false, the algorithm will not use quadratic characters
```

```id=1|
#
# This cell implements simple heuristics for the
# parameters used in the GNFS based on given N
#

rational_factor_base_bound_ratio = 5;    # this factor seemed to work well
algebraic_factor_base_bound_ratio = 10;  # so did this
quadratic_character_base_ratio = 0.10;   # as a percentage of the algebraic factor base

degree = 3;     # hard coded in this toy implementation

a_bound_ratio = 0.004;

def determine_GNFS_bounds(N):
B1 = max(10, ceil(rational_factor_base_bound_ratio*log(N)));
B2 = max(20, ceil(algebraic_factor_base_bound_ratio*log(N)));

else:

a_bound = min(max(50, ceil(a_bound_ratio * N)), (2^16 - 1) );

print 'Parameter Selection for GNFS:'

print 'upper bound on rational prime base (all primes under):', B1
print 'upper bound on algebraic prime base (all first degree primes under):', B2
print 'upper bound on quadratic character prime base (all subsequent primes under):', B3

print 'search bounds for unit term: [', -a_bound, ',', a_bound, ']'

return (B1, B2, B3, degree, a_bound);
```

```id=65|
#
# Note about the representation of prime base elements
# rational primes are represented as (m mod p, p) p prime in QQ
# algebraic primes are represented as (r, p) p prime in QQ, r root of f mod p.
# storing in this form helps sieving and allows common code to be used
# for both
#
```

```id=2|
# This cell defines the function that
# generates the rational factor base
# (rational primes for sieving)

def generate_rational_factor_base(m, Bound):

rational_factor_base = [];

for p in xrange(1,Bound):
if(is_prime(p)):
rational_factor_base.append((m % p, p));

return rational_factor_base;
```

```id=3|
# This cell generate the algebraic factor base
# (first degree prime ideals of order Z[theta] in number field)

# helper functions:

# uses sage to determine roots of f mod p
def get_roots_mod_p(f, p):
return f.change_ring(GF(p)).roots(None, False);

# generates the algebraic factor base
def generate_algebraic_factor_base(f, Bound):

algebraic_factor_base = [];

for p in xrange(Bound):
if(is_prime(p)):
roots_fmodp = get_roots_mod_p(f, p);

for j in xrange(len(roots_fmodp)):
algebraic_factor_base.append((roots_fmodp[j].lift(),p))

return algebraic_factor_base;

for p in xrange(Lower_Bound, Upper_Bound):
if(is_prime(p)):
roots_fmodp = get_roots_mod_p(f, p);

for j in xrange(len(roots_fmodp)):

```

```id=4|
#
# this cell defines helper functions for polynomials
#
#

#
# determines m-arry expansion of N
# and the coefficients of powers of m
def get_polynomial_coefficients(N, m):

coefficient_list = [];

temp = N;

while(0 != temp):
r = temp % m;
temp = (temp - r) / m;
coefficient_list.append(r);

return coefficient_list;

#
# function that tries to generate a
# monic, irreducible polynomial f with root m mod N
# with degree d.
#
def generate_polynomial(polynomial_ring, N, d):
# determine and lower and upper bounds for m

q = 0;

while (1 != q):

u = floor(pow(N, 1.0/d));
l = ceil(pow(N, (2.0*d - 3.0)/(2.0*d*(d-1))));

m = floor(round(uniform(l, u)));

(q,r) = (N).quo_rem(m^d);

f = polynomial_ring(get_polynomial_coefficients(N, m));

return (f, m)

#
# checks if a polynomial is monic and irreducible
#
def is_good_polynomial(f):
return (f.is_monic() and f.is_irreducible())

#
# retries a bunch of times to generate a suitable random polynomial
#
def get_polynomial(polynomial_ring, N, d, retry_count):

found_polynomial = False;

for j in xrange(retry_count):
(f, m) = generate_polynomial(polynomial_ring, N, d);
if is_good_polynomial(f):
found_polynomial = True;
break;

if (found_polynomial):
return (f, m)
else:
return (0,0)
```

```id=18|
#
#    This cell contains the sieving code
#

quo_rem = Integer.quo_rem

#
#    Common code that will take a factor base and sieve it
#
def sieve_interval(interval_to_sieve, a_lowerbound, b, factor_base):

factor_base_count = len(factor_base);

exponent_lists = [ [0 for j in xrange(factor_base_count+1)] for k in xrange(len(interval_to_sieve))]

#
#    determine the sign exponents of the elements in each interval
#

for j in xrange(len(interval_to_sieve)):
if (interval_to_sieve[j] < 0):
exponent_lists[j][factor_base_count] = 1;
interval_to_sieve[j] = abs(interval_to_sieve[j]);

#
#    do the factor base sieving
#

for j in xrange(factor_base_count):
p = factor_base[j][1];
bt = -b*factor_base[j][0] % p;

#
#    Much of the power of the sieving algorithms
#    come from the regular access pattern and
#    advancing through the array p elements at a time
#

# in this case we have our factor bases stored as a pair (t,p)
# such that the value in the sieve in that position
# (for the rational base this is a+b*m and for the algebraic base it is N(a+b*theta)
# is only divisible by p if a = -b*t + k*p, as such we
# use the lower bound of the a range to determine the first
# position in the array to start sieving at advance p positions from there

for k in xrange((bt  - a_lowerbound) % p, len(interval_to_sieve), p):

#
# This loop goes through and calculates the largest integer e
# such that p^e divides the array entry
#

e = 0;
r = 0;

while (0 == r):
if (interval_to_sieve[k] != 0):
(q,r) = quo_rem(interval_to_sieve[k] , p);
if(0 == r):
r = 0;
e = e + 1;
interval_to_sieve[k] = q;
else:
r = 1;
else:
r = 1;

exponent_lists[k][j] = e;

return (interval_to_sieve, exponent_lists)

#
# determines the quadratic character exponent vector
#

qc_expons = [0 for j in xrange(len(quad_char_base))];

qc_expons[j] = Integer((1 - legendre_symbol(a+s*b, q))/2);

return qc_expons;

#
#   function: search_for_smooth_pairs
#   input: 6 parameters:
#   lower bound of a's
#   b
#   list of a+bm, sieved with respect to rational factor base
#   The exponent vector with respect to the rational factor base
#   list of N(a+b*theta) sieved with respect to the algebraic factor base
#   The exponent vector with respect to the algebraic factor base

#   output: a list of triplets of:
#   (a,b) pairs of integers that are smooth with respect to
#         both the algebraic and rational factor bases.
#   the exponent list with respect to the rational factor base
#   the exponent list with respect to the algebraic factor base
#

def search_for_smooth_pairs(a_lowerbound, b, rat_sieve, rat_exp_list, alg_sieve, alg_exp_list, quad_char_base):

smooth_list = [];

for j in xrange(len(rat_sieve)):
if ( (1 == rat_sieve[j]) and (1 == alg_sieve[j]) ):

smooth_list.append(((a_lowerbound+j,b),rat_exp_list[j],alg_exp_list[j], qc_expons));

return smooth_list;

#
# Do the actual sieving
# returns a list of (a,b) pairs along with the rational, algebraic, and quadratic exponents
#

def perform_sieving(f, m, a_bound, rat_factor_base, alg_factor_base, quad_char_base):

# determine the dimension of the space we are working over.
l1 = len(rat_factor_base);
l2 = len(alg_factor_base);

l = l1 + l2 + l3 + 2; # add two for rational and algebraic sign exponents;

d = f.degree()

smooth_element_list = [];

# loop until we have more smooth elements
# than we have dimension

b = 1;

while(len(smooth_element_list) <= l):

rat_interval = [];
alg_interval = [];

for j in xrange(2*a_bound + 1):

a = -a_bound + j;

rat_interval.append(a + b*m); # sieve the value a + b*m
alg_interval.append(Integer(((-b)^d)*f(-a/b))); # sieve the value N(a+b*theta) = (-b)^d * f(-a/b)

(rat_interval, rat_exp_list) = sieve_interval(rat_interval, -a_bound, b, rat_factor_base);

(alg_interval, alg_exp_list) = sieve_interval(alg_interval, -a_bound, b, alg_factor_base);

smooth_pairs_found = search_for_smooth_pairs(-a_bound, b, rat_interval, rat_exp_list, alg_interval, alg_exp_list, quad_char_base);

smooth_element_list.extend(smooth_pairs_found);

print 'found', len(smooth_element_list), 'simultaneously smooth pairs.'

b = b+1;

return smooth_element_list;
```

```id=28|

```

```id=38|
#
#    This cell contains a function that computes the product of the integer pairs
#    as an integer polynomial, and reduces it module the ideal generated by f
#

#
# computes product of linear polynomials mod Ideal generated by f
# (equivalent to doing math in number field
#
def compute_numberfield_product_of_pairs(polynomial_ring, f, integer_pairs, vector):

I = polynomial_ring.ideal(f);

product_polynomial = polynomial_ring([1]);

for j in xrange(len(vector)):

if (1 == vector[j]):

linear_poly = polynomial_ring([integer_pairs[j][0], integer_pairs[j][1]]);
product_polynomial = product_polynomial * linear_poly;
product_polynomial.mod(I);

return product_polynomial;

#
# computes the product of (a + b*m)'s mod N
# of the (a + b*m)'s corresponding to 1s in vector
#
def compute_integer_product_of_pairs(polynomial_ring, f, m, N, integer_pairs, vector):

prod  = 1;

for j in xrange(len(vector)):
if (1 == vector[j]):
prod  = prod*(integer_pairs[j][0] + m*integer_pairs[j][1]) % N;

return prod;

#
# computes the difference of squares u^2 - v^2
# and returns (u+v) and (u-v)
#
def compute_difference_of_squares(polynomial_ring, f, m, N, integer_pairs, vector):

found_squares = False;

u_plus_v = 0;
u_minus_v = 0;

ints_mod_N = ZZ.quo(ZZ.ideal(N));

vsquared = ints_mod_N(compute_integer_product_of_pairs(polynomial_ring, f, m, N, integer_pairs, vector));

if ( is_square(vsquared)):

beta_squared = compute_numberfield_product_of_pairs(polynomial_ring, f, integer_pairs, vector);
beta = find_square(f, beta_squared, polynomial_ring);

if (False != beta):

u = (beta(m)) % N;
v = vsquared.sqrt().lift();
u_plus_v = (u + v) % N;
u_minus_v = (u - v) % N;

found_squares = True;

else:
print 'failed to find a square root in number field.'
else:
print 'integer was not square'

return (found_squares, u_plus_v, u_minus_v);
```

```id=7|
#
#    Cheater Helper Functions
#
#    These are functions that I was too lame to implement myself
#    And Hence relied on sage's built in functionality.
#

ecm_instance = ECM();

def factor_prime_power(N):
# The GNFS doesn't work one prime powers
# so we use ecm to factor,
# in reality,
# we would apply a heuristic on the best way to determine the prime and exponent

ecm_factors = ecm_instance.factor(N);

prime_power_factorization = [(ecm_factors[0], len(ecm_factors))]

return Factorization(prime_power_factorization);

#
#    This simple function does all the linear algebra (thank you sage!)
#
def find_kernel_vectors(M):
return M.kernel().basis_matrix().rows();

#
# In reality this would be done with the CRT.
#
def find_square(f, beta_squared, polynomial_ring):
# computes the square root of beta_squared
# (a polynomial over ZZ of degree less than d, that represents the element in the order ZZ[theta])
# and returns the polynomial representing the square root.

K.<a> = NumberField(f);
beta2 = beta_squared(a);
if(not beta2.is_square()):
print 'The supposedly found square is not square!'
return False;
return polynomial_ring(beta2.sqrt().list());
```

```id=9|
#
# This is the factoring algorithm
# It factors N, and returns a sage factorization object of N
#

def GNFS_Factoring_Algorithm(N):

# determine if this is a good number to use the GNFS on
# if it is not (i.e. it is a prime power)
# call the specialized prime power factorization function

if(is_prime_power(N)):

print N, 'is a prime power, reducing to using ECM to factor'

return factor_prime_power(N);

# determine the algorithm bounds
(B1, B2, B3, d, a_bound) = determine_GNFS_bounds(N);

R.<x> = ZZ[];

(f, m) = get_polynomial(R, N, d, 20);

if((0 == f) and (0 == m)):

# if the polynomial selection code did not find a degree d
# polynomial in 20 tries, just use the built-in factoring
# algorithm, because N is too small for the GNFS to work
# at that point

return factor(N);

# get the rational factor base
rational_factor_base = generate_rational_factor_base(m, B1);

# get the algebraic factor base
algebraic_factor_base = generate_algebraic_factor_base(f, B2);

# get the quadratic character base

#
# get a list of smooth elements
#

smooth_element_list = perform_sieving(f, m, a_bound, rational_factor_base, algebraic_factor_base, quadratic_character_base);

#
#    parse out the list of smooth elements into a list of integer pairs,
#

integer_pairs = [smooth_element_list[k][0] for k in xrange(len(smooth_element_list))];
exponent_vectors = [];

#
# use the smooth element list vectors to make a matrix
#

for k in xrange(len(smooth_element_list)):
exponent_vectors.extend(smooth_element_list[k][1]);
exponent_vectors.extend(smooth_element_list[k][2]);
exponent_vectors.extend(smooth_element_list[k][3]);

num_expons = len(smooth_element_list[0][1]) + len(smooth_element_list[0][2]) + len(smooth_element_list[0][3]);

M = matrix(GF(2), len(smooth_element_list), exponent_vectors )

solutions = find_kernel_vectors(M);

nontrivial_first_factor = False;
nontrivial_second_factor = False;

k = 0

#
#    Loop over the vectors that sum to zero to try and find one
#    That leads to a non trivial factorization
#
while ((k < len(solutions)) and (not nontrivial_first_factor) and (not nontrivial_second_factor)):

(found_squares, u_plus_v, u_minus_v) = compute_difference_of_squares(R, f, m, N, integer_pairs, solutions[k]);

if(found_squares):

first_factor_of_N = gcd(u_plus_v, N);

second_factor_of_N = gcd(u_minus_v, Integer(N/first_factor_of_N));

if((1 != first_factor_of_N) and (N != first_factor_of_N)):
nontrivial_first_factor = True;
if((1 != second_factor_of_N) and (N != second_factor_of_N)):
nontrivial_second_factor = True;
else:
print 'failed to find a nontrivial factor.'

else:
print 'failed to find squares.'

k = k + 1;

factors_of_N = [];

N_remaining = N;

if(nontrivial_first_factor):
factors_of_N.append(first_factor_of_N);
N_remaining = Integer(N_remaining/first_factor_of_N)

if(nontrivial_second_factor):
remaining_second_factor = gcd(second_factor_of_N, N_remaining);
factors_of_N.append(remaining_second_factor);
N_remaining = Integer(N_remaining/second_factor_of_N);

if(1 != N_remaining):
factors_of_N.append(N_remaining);

factorization_of_N = factor(1);

#
#    Recursively factor non trivial factors
#    Or N, if we completely failed to find a factor
#

for j in xrange(len(factors_of_N)):
factorization_of_N = factorization_of_N * GNFS_Factoring_Algorithm(factors_of_N[j]);

return factorization_of_N;
```

```id=68|
#
# Some test cases follow:
#
```

```id=29|
time GNFS_Factoring_Algorithm(45113);
///
Parameter Selection for GNFS:
upper bound on rational prime base (all primes under):                                       54
upper bound on algebraic prime base (all first degree primes under):                                       108
upper bound on quadratic character prime base (all subsequent primes under):                                       227
search bounds for unit term: [ -181 , 181 ]
found 25 simultaneously smooth pairs.
found 33 simultaneously smooth pairs.
found 60 simultaneously smooth pairs.
found 65 simultaneously smooth pairs.
229 is a prime power, reducing to using ECM to factor
197 is a prime power, reducing to using ECM to factor
197 * 229
CPU time: 0.60 s,  Wall time: 1.24 s
```

```id=69|
197 * 229
///
45113
```

```id=50|
GNFS_Factoring_Algorithm(99999);
///
Parameter Selection for GNFS:
upper bound on rational prime base (all primes under):                                       58
upper bound on algebraic prime base (all first degree primes under):                                       116
upper bound on quadratic character prime base (all subsequent primes under):                                       244
search bounds for unit term: [ -400 , 400 ]
found 34 simultaneously smooth pairs.
found 45 simultaneously smooth pairs.
found 82 simultaneously smooth pairs.
failed to find a nontrivial factor.
Parameter Selection for GNFS:
upper bound on rational prime base (all primes under):                                       30
upper bound on algebraic prime base (all first degree primes under):                                       60
upper bound on quadratic character prime base (all subsequent primes under):                                       126
search bounds for unit term: [ -50 , 50 ]
found 18 simultaneously smooth pairs.
found 27 simultaneously smooth pairs.
found 45 simultaneously smooth pairs.
Parameter Selection for GNFS:
upper bound on rational prime base (all primes under):                                       25
upper bound on algebraic prime base (all first degree primes under):                                       49
upper bound on quadratic character prime base (all subsequent primes under):                                       103
search bounds for unit term: [ -50 , 50 ]
found 17 simultaneously smooth pairs.
found 24 simultaneously smooth pairs.
found 44 simultaneously smooth pairs.
failed to find a nontrivial factor.
failed to find a nontrivial factor.
failed to find a nontrivial factor.
3 is a prime power, reducing to using ECM to factor
41 is a prime power, reducing to using ECM to factor
3 is a prime power, reducing to using ECM to factor
271 is a prime power, reducing to using ECM to factor
3^2 * 41 * 271
```

```id=40|
GNFS_Factoring_Algorithm(784352)
///
Parameter Selection for GNFS:
upper bound on rational prime base (all primes under):                                       68
upper bound on algebraic prime base (all first degree primes under):                                       136
upper bound on quadratic character prime base (all subsequent primes under):                                       286
search bounds for unit term: [ -3138 , 3138 ]
found 29 simultaneously smooth pairs.
found 68 simultaneously smooth pairs.
found 83 simultaneously smooth pairs.
found 123 simultaneously smooth pairs.
Parameter Selection for GNFS:
upper bound on rational prime base (all primes under):                                       44
upper bound on algebraic prime base (all first degree primes under):                                       88
upper bound on quadratic character prime base (all subsequent primes under):                                       185
search bounds for unit term: [ -50 , 50 ]
found 20 simultaneously smooth pairs.
found 47 simultaneously smooth pairs.
found 58 simultaneously smooth pairs.
16 is a prime power, reducing to using ECM to factor
Parameter Selection for GNFS:
upper bound on rational prime base (all primes under):                                       30
upper bound on algebraic prime base (all first degree primes under):                                       60
upper bound on quadratic character prime base (all subsequent primes under):                                       126
search bounds for unit term: [ -50 , 50 ]
found 19 simultaneously smooth pairs.
found 45 simultaneously smooth pairs.
failed to find a nontrivial factor.
2 is a prime power, reducing to using ECM to factor
193 is a prime power, reducing to using ECM to factor
127 is a prime power, reducing to using ECM to factor
2^5 * 127 * 193
```

```id=57|

```

```id=58|
#
#    Factoring test code
#    This function will randomly generate an integer and factor it with the GNFS
#
#    It fails sometimes, due to stuff like low memory conditions, and bugs
#

def test_GNFS():

N = Integer(ceil(uniform(1, 1000000)));

print 'Factoring N =', N

GNFS_Factorization = GNFS_Factoring_Algorithm(N);

if (GNFS_Factorization.value() != N):
print 'Test Case N =', N, ' FAILED!!!'
print 'says factorization is:', GNFS_Factorization
return False

print GNFS_Factorization

print 'Test Case PASSED!'

return True
```

```id=56|
test_GNFS()
///
Factoring N = 606063
Parameter Selection for GNFS:
upper bound on rational prime base (all primes under):                                       67
upper bound on algebraic prime base (all first degree primes under):                                       134
upper bound on quadratic character prime base (all subsequent primes under):                                       282
search bounds for unit term: [ -2425 , 2425 ]
found 31 simultaneously smooth pairs.
found 43 simultaneously smooth pairs.
found 85 simultaneously smooth pairs.
3 is a prime power, reducing to using ECM to factor
202021 is a prime power, reducing to using ECM to factor
3 * 202021
Test Case PASSED!
True
```

```id=60|
#
#    At first, when reading up on the General Number Field Sieve algorithm
#    I had a hard time understanding the Quadratic character portion of
#    The algorithm, as such, I set this flag to test just what happens if
#    it is not used
#    observe that when the flag is set to false, the algorithm takes longer
#    and has many more errors about failing to find a square in the number field
#

GNFS_Factoring_Algorithm(784352)
///
Parameter Selection for GNFS:
upper bound on rational prime base (all primes under):                                       68
upper bound on algebraic prime base (all first degree primes under):                                       136
upper bound on quadratic character prime base (all subsequent primes under):                                       136
search bounds for unit term: [ -3138 , 3138 ]
found 48 simultaneously smooth pairs.
found 101 simultaneously smooth pairs.
The supposedly found square is not square!
failed to find a square root in number field.
failed to find squares.
failed to find a nontrivial factor.
Parameter Selection for GNFS:
upper bound on rational prime base (all primes under):                                       42
upper bound on algebraic prime base (all first degree primes under):                                       84
upper bound on quadratic character prime base (all subsequent primes under):                                       84
search bounds for unit term: [ -50 , 50 ]
found 40 simultaneously smooth pairs.
The supposedly found square is not square!
failed to find a square root in number field.
failed to find squares.
Parameter Selection for GNFS:
upper bound on rational prime base (all primes under):                                       35
upper bound on algebraic prime base (all first degree primes under):                                       70
upper bound on quadratic character prime base (all subsequent primes under):                                       70
search bounds for unit term: [ -50 , 50 ]
found 24 simultaneously smooth pairs.
found 53 simultaneously smooth pairs.
Parameter Selection for GNFS:
upper bound on rational prime base (all primes under):                                       32
upper bound on algebraic prime base (all first degree primes under):                                       63
upper bound on quadratic character prime base (all subsequent primes under):                                       63
search bounds for unit term: [ -50 , 50 ]
found 23 simultaneously smooth pairs.
found 50 simultaneously smooth pairs.
The supposedly found square is not square!
failed to find a square root in number field.
failed to find squares.
4 is a prime power, reducing to using ECM to factor
127 is a prime power, reducing to using ECM to factor
2 is a prime power, reducing to using ECM to factor
4 is a prime power, reducing to using ECM to factor
193 is a prime power, reducing to using ECM to factor
2^5 * 127 * 193
```

```id=63|
```id=64|