20150313, 19:14  #1 
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 20150313 at 20:04 
20150313, 23:00  #2 
Tribal Bullet
Oct 2004
2·3·19·31 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.

20150314, 00:18  #3  
Sep 2011
3·19 Posts 
Quote:
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 20150314 at 00:19 

20150314, 19:55  #4 
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) = 210^{2} (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) = 210^{2} = 1760 mod 2117 and: φ (7+6i) = 283^{2} = 1760 mod 2117 so: 283^{2} = 210^{2} = 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 20150314 at 19:57 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Ideas for the future beyond justkeepencrunching  Dubslow  NFS@Home  13  20150202 22:25 
two ideas for NPLB  MiniGeek  No Prime Left Behind  16  20080301 23:32 
GROUP IDEAS  TTn  15k Search  15  20030923 16:28 
Domain name ideas...  Xyzzy  Lounge  17  20030324 16:20 
Couple of ideas/things to do  Stormblade  Lounge  12  20020820 02:21 