Some ideas regarding NFS...

[paul0]

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.

[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.

[paul0]

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) = x² + 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 β = γ²,
β = λ² (the 2nd square root)
So we have:
φ(β) = φ(β) mod n
factoring β on both sides in different ways:
φ(γ) * φ(γ) = φ(λ) * φ(λ) mod n

[paul0]

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²
(4+i)*(8+19i) = 13+84i = (7+6i)²

So, (7+6i)² 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² = 1760 mod 2117
and:
φ (7+6i) = 283² = 1760 mod 2117
so:
283² = 210² = 1760 mod 2117
which factors 2117.


Consider a 4th power:
β = γ⁴
and we have two different ways of factoring β:
β = γ²* γ²
and
β = γ*γ*γ*γ
So we have:
φ(γ²) * φ(γ²) = φ(γ) * φ(γ) * φ(γ) * φ(γ) mod n
(in Z[i], an example is -6887 + 2184i = (13 + 84i)*(13 + 84i) = (7 + 6i)⁴)
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.