mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2015-03-13, 19:14   #1
paul0
 
Sep 2011

3×19 Posts
Default 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
paul0 is offline   Reply With Quote
Old 2015-03-13, 23:00   #2
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

2·3·19·31 Posts
Default

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.
jasonp is offline   Reply With Quote
Old 2015-03-14, 00:18   #3
paul0
 
Sep 2011

3·19 Posts
Default

Quote:
Originally Posted by jasonp View Post
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
paul0 is offline   Reply With Quote
Old 2015-03-14, 19:55   #4
paul0
 
Sep 2011

5710 Posts
Default

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
paul0 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Ideas for the future beyond just-keep-encrunching Dubslow NFS@Home 13 2015-02-02 22:25
two ideas for NPLB Mini-Geek No Prime Left Behind 16 2008-03-01 23:32
GROUP IDEAS TTn 15k Search 15 2003-09-23 16:28
Domain name ideas... Xyzzy Lounge 17 2003-03-24 16:20
Couple of ideas/things to do Stormblade Lounge 12 2002-08-20 02:21

All times are UTC. The time now is 11:38.

Sat Mar 6 11:38:22 UTC 2021 up 93 days, 7:49, 0 users, load averages: 1.63, 1.54, 1.40

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.