Could someone please check my calculations?

Sam Kennedy · 2012-12-26, 19:21

I'm working on generating polynomials for the MPQS, everything is working, but I'm not sure if it's correct.

n = 61063
M = 50

d =~ a prime around sqrt(61063/2)/50, with a residue n mod p = 3
A = d^2 = 3^2 = 9

Now computing B is a little bit more involved:
h = modular square root of 61063 mod 3 = 1
v = modular inverse of 2h * ((n - h^2)/d) mod d
= 2 * ((61063 - 1)/3) mod 3 = 1
B = h + vd mod A
= 1 + (1*3) mod 9 = 4

So the polynomial will be y(x) = (9x + 4)^2 - 61063
And I will plug in values of x from -50 to 50.

For the sake of example, let's pretend that the first value of x (-50) produces a smooth value, would the relation be stored as:
x = -50, y = 137853
or
x = -50, y = 15317
or
x = -446, y = 137853
or
x = -446, y = 15317

I'm thinking the last one, but I got an E in maths and dropped the course, so not exactly qualified to be stating facts

Thank You

henryzz · 2012-12-26, 22:03

The third option would work. msieve stores its relations in its savefile by recording a, b, x and the factorization I think. I am not sure why. If someone could give the way to make msieve read relations with a=1 b=0 I would be grateful. I can't quite understand the format.

jasonp · 2012-12-27, 08:52

The savefile lists a, b and x but expresses the factorization as a list of array offsets, not a list of primes. Then you have an 'L' and the two large primes of the relation, one or both of which may be 1.

2012-12-26, 19:21	#1
Sam Kennedy Oct 2012 1010010₂ Posts	Could someone please check my calculations? I'm working on generating polynomials for the MPQS, everything is working, but I'm not sure if it's correct. n = 61063 M = 50 d =~ a prime around sqrt(61063/2)/50, with a residue n mod p = 3 A = d^2 = 3^2 = 9 Now computing B is a little bit more involved: h = modular square root of 61063 mod 3 = 1 v = modular inverse of 2h * ((n - h^2)/d) mod d = 2 * ((61063 - 1)/3) mod 3 = 1 B = h + vd mod A = 1 + (1*3) mod 9 = 4 So the polynomial will be y(x) = (9x + 4)^2 - 61063 And I will plug in values of x from -50 to 50. For the sake of example, let's pretend that the first value of x (-50) produces a smooth value, would the relation be stored as: x = -50, y = 137853 or x = -50, y = 15317 or x = -446, y = 137853 or x = -446, y = 15317 I'm thinking the last one, but I got an E in maths and dropped the course, so not exactly qualified to be stating facts Thank You

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Factoring Calculations	harishdeen	Homework Help	14	2015-03-31 15:26
Interval calculations with a given alpha	CRGreathouse	Math	10	2010-04-09 06:23
First check and double check llrnet servers.	opyrt	Prime Sierpinski Project	3	2009-01-02 01:50
Is based 10 used for calculations?	Googol	Information & Answers	2	2007-07-27 03:09
HOW MANY CALCULATIONS AT ONCE??	alienz	Lounge	19	2003-07-06 03:11

2012-12-26, 22:03	#2
henryzz Just call me Henry "David" Sep 2007 Liverpool (GMT/BST) 2³×7×107 Posts	The third option would work. msieve stores its relations in its savefile by recording a, b, x and the factorization I think. I am not sure why. If someone could give the way to make msieve read relations with a=1 b=0 I would be grateful. I can't quite understand the format.

2012-12-27, 08:52	#3
jasonp Tribal Bullet Oct 2004 5×709 Posts	The savefile lists a, b and x but expresses the factorization as a list of array offsets, not a list of primes. Then you have an 'L' and the two large primes of the relation, one or both of which may be 1.