mersenneforum.org Some ideas regarding NFS...
 Register FAQ Search Today's Posts Mark Forums Read

 2015-03-13, 19:14 #1 paul0   Sep 2011 3·19 Posts Some ideas regarding NFS... If the ring produced by NFS is not a UFD, then the square produced in the ring can be factored in different ways. I was thinking, is it possible to use these different factorizations to produce different congruent squares? I believe, to implement such an algorithm, these questions must be answered: 1. How often will multiple square roots happen? Is this a rare phenomenon? 2. How will the different square roots be found? 3. How much will this reduce the runtime of the algorithm? I believe this will halve the size of numbers to be sieved, since there is no rational side. If we do this on (S)NFS with polynomial f(x), then finding a square with two different roots will allows us to factor any number whose poly is f(x), since the square can always be reused. Last fiddled with by paul0 on 2015-03-13 at 20:04
 2015-03-13, 23:00 #2 jasonp Tribal Bullet     Oct 2004 2·52·71 Posts The congruence of squares is technically a congruence of square integers modulo the number to be factored, not squares of number field elements. So there's always going to be a rational side that forms one half of the congruence you need.
2015-03-14, 00:18   #3
paul0

Sep 2011

1110012 Posts

Quote:
 Originally Posted by jasonp The congruence of squares is technically a congruence of square integers modulo the number to be factored, not squares of number field elements. So there's always going to be a rational side that forms one half of the congruence you need.
Consider f(x) = x2 + 1, m=46, n=2117
let β = -11+3i.
φ(-11+3i) = -11+3*46 = 127 mod 2117
Using the homomorphism and factoring -11+3i in different ways, we can generate many more numbers that are congruent to 127 mod 2117:
φ(1+i) * φ(1+2i) * φ(2+3i) = (1+46) (1+2*46) (2+3*46) = 611940 = 127 mod 2117
φ(-1+3i) * φ(2+3i) = (-1+3*46) * (2+3*46) = 19180 = 127 mod 2117

So, I've created congruences without a rational side by taking the different ways that β factors in Z[i] (an actual factorization would use 13+84i = (4+i)*(8+19i)). I was thinking, if it was possible to create a congruence of squares this way? As in my previous post, what if β is a square in Z[α] and it factors into different square roots because the ring is not a UFD, then use those square roots to create a congruence in squares like this:
let β = γ2,
β = λ2 (the 2nd square root)
So we have:
φ(β) = φ(β) mod n
factoring β on both sides in different ways:
φ(γ) * φ(γ) = φ(λ) * φ(λ) mod n

Last fiddled with by paul0 on 2015-03-14 at 00:19

 2015-03-14, 19:55 #4 paul0   Sep 2011 3·19 Posts Still playing around with this... An actual factorization choose (4+i) and (8+19i) as relations form a square since: (4+m)*(8+19m) = 2102 (4+i)*(8+19i) = 13+84i = (7+6i)2 So, (7+6i)2 and (4+i)*(8+19i) are just two different ways to factor 13+84i. Using the homomorphism: φ(13+84i) = 1760 mod 2117 Because the homomorphism is multiplicative, we can factor 13+84i and the congruence still works: φ(4+i)*φ(8+19i) = 2102 = 1760 mod 2117 and: φ (7+6i) = 2832 = 1760 mod 2117 so: 2832 = 2102 = 1760 mod 2117 which factors 2117. Consider a 4th power: β = γ4 and we have two different ways of factoring β: β = γ2* γ2 and β = γ*γ*γ*γ So we have: φ(γ2) * φ(γ2) = φ(γ) * φ(γ) * φ(γ) * φ(γ) mod n (in Z[i], an example is -6887 + 2184i = (13 + 84i)*(13 + 84i) = (7 + 6i)4) This gives us an easy way of constructing a congruence of squares. The congruence works, I always get a trivial factor. Why? What makes it different from the previous example? Both just finds different factorizations of an element in the ring. I apologize if I have a blatant misunderstanding of this, but I there is nowhere else to ask, really. Last fiddled with by paul0 on 2015-03-14 at 19:57

 Similar Threads Thread Thread Starter Forum Replies Last Post Dubslow NFS@Home 13 2015-02-02 22:25 Mini-Geek No Prime Left Behind 16 2008-03-01 23:32 TTn 15k Search 15 2003-09-23 16:28 Xyzzy Lounge 17 2003-03-24 16:20 Stormblade Lounge 12 2002-08-20 02:21

All times are UTC. The time now is 03:52.

Fri Dec 2 03:52:18 UTC 2022 up 106 days, 1:20, 0 users, load averages: 0.73, 0.94, 1.06