linear substitution and sieving

[bhelmes]

A peaceful and pleasant day for you,


I have a sieving construction for f(n)=2n²-1,
(that means that every prime p with p | f(n) sieves at two n1 and n2 periodically with p the field for n=0 ... n=n_max)


for example p=7=2*2²-1 sieves at n1=k*7+2 and n2=k*7+5, k element N


If I calculate the first 83 primes with remembering the depending n1 and n2
and make a linear substitution n0=99 p(n0)=1153
so that n=1153m+99 and

f(m)=2*(1153m+99)²-1
=2*(1153²m²+2*1153*99m+99²)-1
=2*1153²m²+4*1153*99m+2*9801-1

=2*1153²m²+4*1153*99m+19601 | /1153
=2*1153m²+4*99m+17



how do I transform the n1 and n2 of the preceding primes p1 up to p83 for the resulting polynom.


This is not a very difficult problem, I think, and

if someone has a good explication, I will be grateful.



Have a good evening,

Bernhard

[Dr Sardonicus]

I'm a little puzzled. The first 83 primes p == 1 or 7 (mod 8) are

[7, 17, 23, 31, 41, 47, 71, 73, 79, 89, 97, 103, 113, 127, 137, 151, 167, 191, 193, 199, 223, 233, 239, 241, 257, 263, 271, 281, 311, 313, 337, 353, 359, 367, 383, 401, 409, 431, 433, 439, 449, 457, 463, 479, 487, 503, 521, 569, 577, 593, 599, 601, 607, 617, 631, 641, 647, 673, 719, 727, 743, 751, 761, 769, 809, 823, 839, 857, 863, 881, 887, 911, 919, 929, 937, 953, 967, 977, 983, 991, 1009, 1031, 1033]

And I'm not sure what you're asking. Given an r for which 2*r² - 1 == 0 (mod p), we have

((k*p + r)^2 - 1)/p = p*k^2 + 2*k*r + (r^2 - 1)/p.

As to computing an r for a given p,

Given p == 1 or 7 (mod 8), the Pari-GP command sqrt(Mod(1/2, p)) will return Mod(r, p) for the r in the interval (0, p/2).

The Pari-GP command factormod(x^2 - 1/2, p) will find both square roots of 1/2 (mod p)

If p == 7 (mod 8), (Mod(1/2,p)^((p+1)/4) will give one of the values of Mod(r,p).

[bhelmes]

Dear Dr Sardonicus

Originally Posted by Dr Sardonicus

I'm a little puzzled. The first 83 primes p == 1 or 7 (mod 8) are

[7, 17, 23, 31, 41, 47, 71, 73, 79, 89, 97, 103, 113, 127, 137, 151, 167, 191, 193, 199, 223, 233, 239, 241, 257, 263, 271, 281, 311, 313, 337, 353, 359, 367, 383, 401, 409, 431, 433, 439, 449, 457, 463, 479, 487, 503, 521, 569, 577, 593, 599, 601, 607, 617, 631, 641, 647, 673, 719, 727, 743, 751, 761, 769, 809, 823, 839, 857, 863, 881, 887, 911, 919, 929, 937, 953, 967, 977, 983, 991, 1009, 1031, 1033]

The first prime p concerning the polynomial f(n)=2n²-1 (with p|f(n)) are


[7, 17, 31, 71, 97, 127, 23, 199, 241, 41, 337, 449, 73, 577, 647, 103, 47, 881, 967, 151, 1151, 1249, 193, 1567, 257, 113, 89, 311, 2311, 79, 2591, 2887, 3041, 457, 3361, 3527, 3697, 4049, 4231, 631, 271, 4801, 4999, 743, 5407, 137, 263, 6271, 6961, 313, 1063]
<a href="https://oeis.org/search?q=A144861">A144861</a>



The primes are the same, but the sequence is different.


I refer to (my) quadratic sieve algorithm, described by
http://devalco.de/quadr_Sieb_2x%5E2-1.php


I think you are familiar with this algorithm.


The question was:
First I sieve from n=1 to n=98,
store the found primes p and the roots n1 and n2 concerning p,

found the last prime at n=99 so that f(99)=17*1153
and make a linear substitution with n=1153m+99 for f(n)
I get a new quadratic polynomial f(m) which I want to sieve further.


I guess you have to transform the n1s and n2s by the same substitution mod p


(How far can I sieve the new polynomial until I get 2 new primes as factor of f(m) at the same m.)




I want to improve the algorithm by using the same presieved primes for different "curves" and think that this is an improvement.


Thanks for your patience, I am trying to improve my mathematical skills
and I am thankful for your clear explications. Sometimes the Romulus Interpreter is helpful.



Greeting

Bernhard

[LaurV]

Originally Posted by bhelmes

Red ball for putting cmd, unc, and petrw in the same paragraph!

[Dr Sardonicus]

It's still not clear to me what you are trying to accomplish.

If I understand correctly, for n > 1, what you call f'(n) is the cofactor of f(n) = 2*n^2 - 1 remaining after you have divided out all prime factors of f(k) for 1 < k < n. This cofactor can be 1 (e.g. n = 5). For any prime p == 1 or 7 (mod 8) there is an r in (0,p/2) for which p divides 2*r^2 - 1, so the prime factors of f(k), 1 < k < n, include all primes == 1 or 7 (mod 8) which are less than 2*n. Thus, if the cofactor is not 1, it is a prime congruent to 1 or 7 (mod 8) which is greater than 2*n.

As to your substitutions, again it is not clear what you are trying to accomplish. For each p, there are two (equal and opposite) residue classes of n (mod p) for which p divides f(n). If you're only looking at values of n for which f(n) is divisible by all primes in a given set of k primes, that is a set of 2^k residue classes modulo the product of those primes. If you're asking for a value of m such that the cofactor of f(m) after dividing out all factors of primes in a fixed list is composite, that question makes sense. For your list,

[7, 17, 31, 71, 97, 127, 23, 199, 241, 41, 337, 449, 73, 577, 647, 103, 47, 881, 967, 151, 1151, 1249, 193, 1567, 257, 113, 89, 311, 2311, 79, 2591, 2887, 3041, 457, 3361, 3527, 3697, 4049, 4231, 631, 271, 4801, 4999, 743, 5407, 137, 263, 6271, 6961, 313, 1063]

the first m for which the cofactor of 2*m^2 - 1 remaining after all factors of primes on the above list have been divided out has two distinct prime factors, is 1022; 2*1022^2 - 1 = 191*10937.

[bhelmes]

Originally Posted by Dr Sardonicus

If I understand correctly, for n > 1, what you call f'(n) is the cofactor of f(n) = 2*n^2 - 1 remaining after you have divided out all prime factors of f(k) for 1 < k < n. This cofactor can be 1 (e.g. n = 5). For any prime p == 1 or 7 (mod 8) there is an r in (0,p/2) for which p divides 2*r^2 - 1, so the prime factors of f(k), 1 < k < n, include all primes == 1 or 7 (mod 8) which are less than 2*n. Thus, if the cofactor is not 1, it is a prime congruent to 1 or 7 (mod 8) which is greater than 2*n.

Exact right

Originally Posted by Dr Sardonicus

As to your substitutions, again it is not clear what you are trying to accomplish.

I am trying to parallize the algorithm and to improve the runtime.

Originally Posted by Dr Sardonicus

If you're asking for a value of m such that the cofactor of f(m) after dividing out all factors of primes in a fixed list is composite, that question makes sense. For your list,

[7, 17, 31, 71, 97, 127, 23, 199, 241, 41, 337, 449, 73, 577, 647, 103, 47, 881, 967, 151, 1151, 1249, 193, 1567, 257, 113, 89, 311, 2311, 79, 2591, 2887, 3041, 457, 3361, 3527, 3697, 4049, 4231, 631, 271, 4801, 4999, 743, 5407, 137, 263, 6271, 6961, 313, 1063]

the first m for which the cofactor of 2*m^2 - 1 remaining after all factors of primes on the above list have been divided out has two distinct prime factors, is 1022; 2*1022^2 - 1 = 191*10937.

I think I can be sure that in this case m>n_max.


Therefore I can sieve out the primes with p|f(n) in the interval [2, n_max]
and use these primes for p | f(n+1)"="f(m) if p>1
and sieve the second polynomial f(m) up to m_max=n_max


This is a kind of prime generator, useful for special tasks, which I do not know yet.



Thanks for your patience.

[VBCurtis]

Originally Posted by bhelmes

This is a kind of prime generator, useful for special tasks, which I do not know yet.
Thanks for your patience.

It's not a prime generator. Nothing about your work "generates" primes. You merely have possible primes left after your filtering, just like any other sieving software. Nothing about your method is faster than regular sieving; it's just your fixation on this specific polynomial that convinces you it's special.

[Dr Sardonicus]

I note OEIS A005528, Størmer numbers or arc-cotangent irreducible numbers: numbers k such that the largest prime factor of k^2 + 1 is >= 2*k.

The sequence of positive integers n for which 2*n^2 - 1 has a primitive prime factor (i.e. a prime factor which does not divide 2*m^2 - 1 for positive integers m < n) likely has similar properties.

[CRGreathouse]

Originally Posted by Dr Sardonicus

The sequence of positive integers n for which 2*n^2 - 1 has a primitive prime factor (i.e. a prime factor which does not divide 2*m^2 - 1 for positive integers m < n) likely has similar properties.

Definitely. Just be careful, since 2n^2 - 1 isn't monic, so theorem 1.4 doesn't apply directly. I'm not sure if shifting it will shift the density or not. (Probably not, but as they say: Доверяй, но проверяй.)

[Dr Sardonicus]

Originally Posted by CRGreathouse

Definitely. Just be careful, since 2n^2 - 1 isn't monic, so theorem 1.4 doesn't apply directly. I'm not sure if shifting it will shift the density or not. (Probably not, but as they say: Доверяй, но проверяй.)

I thought about it not being monic. For a given p == 1 or 7 (mod 8) the k in the sequence for which 2*k^2 - 1 has p as primitive factor is (in Pari-GP notation)

k = sqrt(Mod(1/2,p)). This gives the square root of 1/2 (mod p) in (0, p/2) which is what we want. Now 1/2 "looks like" a fixed value, but of course it's (p+1)/2 (mod p).

If r = sqrt(Mod(2, p)) then k is either r^-1 or p - r^-1 (mod p), no way I see to tell which without doing the calculation. And I don't know how it affects the distribution.

To me, a more interesting problem is determining, for a given n, whether f(n) = 2*n^2 - 1 has any primitive factors. I don't see any way other than tedious checking. "Everybody knows" (but nobody knows how to prove) that f(n) is prime for infinitely many n. Clearly, each prime p == 1 or 7 (mod 8) is a primitive factor of f(n) for some n -- namely, the square root of 1/2 (mod p) in (0, p/2).

So n < p/2. The best lower bound I can see is n >= sqrt((p+1)/2) which is (as indicated above) conjectured to occur infinitely often. So in order to exclude f(n) having a primitive factor by calculating all the values k <= n corresponding to some p, it would seem you have to check all the primes == 1 or 7 (mod 8) up to 2*n^2 - 1. Or, check for divisibility by all primitive factors of 2*k^2 - 1 for all k < n.

Those... seem... ... ... ... kinda... ... ... ... ... ... ... ... ... ... slow.

Better just to factor 2*n^2 - 1, and then check whether the largest prime factor is > 2*n.

I also have no idea of the number of n <= X for which f(n) has no primitive factors. Positive density?

The best I can do offhand is "there are infinitely many such n," namely the n > 1 for which 2*n^2 - 1 is a perfect square. These grow exponentially, so don't affect density.

[bhelmes]

Originally Posted by Dr Sardonicus

And I'm not sure what you're asking. Given an r for which 2*r² - 1 == 0 (mod p), we have

((k*p + r)^2 - 1)/p = p*k^2 + 2*k*r + (r^2 - 1)/p.

(2(k*p + r)^2 - 1)/p = 2p*k^2 + 4*k*r + (2r^2 - 1)/p


If I choose a linear substitution with p=2n²-1 and the same n,
so that m=k*p+n then I will always get a quadratic polynomial like
f(m)=am²+bm+1


I can make the substitution recursiv,

so that f(m)-1 has always the factor m


How about a quadratic sieve with a book keeping of the polynomial ?