 mersenneforum.org Some ideas regarding NFS...
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read 2015-03-13, 19:14 #1 paul0   Sep 2011 718 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 33·131 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

3×19 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  Thread Tools Show Printable Version Email this Page 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 02:53.

Sun Apr 18 02:53:39 UTC 2021 up 9 days, 21:34, 0 users, load averages: 1.41, 1.61, 1.57

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.