 mersenneforum.org > Math linear substitution and sieving
 Register FAQ Search Today's Posts Mark Forums Read 2020-11-08, 17:43 #1 bhelmes   Mar 2016 5438 Posts linear substitution and sieving 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 Last fiddled with by bhelmes on 2020-11-08 at 17:44   2020-11-09, 14:15 #2 Dr Sardonicus   Feb 2017 Nowhere 23×7×89 Posts 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*r2 - 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).   2020-11-10, 16:14   #3
bhelmes

Mar 2016

5×71 Posts Dear Dr Sardonicus

Quote:
 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

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   2020-11-11, 10:36   #4
LaurV
Romulan Interpreter

Jun 2011
Thailand

24·13·47 Posts Quote:
 Originally Posted by bhelmes    Red ball for putting cmd, unc, and petrw in the same paragraph!    2020-11-11, 15:50 #5 Dr Sardonicus   Feb 2017 Nowhere 23×7×89 Posts 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 2k 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, Code: [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. Last fiddled with by Dr Sardonicus on 2020-11-12 at 00:45 Reason: Add "has two distinct prime factors"   2020-11-12, 01:52   #6
bhelmes

Mar 2016

5·71 Posts Quote:
 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

Quote:
 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.

Quote:
 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, Code: [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.      2020-11-12, 02:56   #7
VBCurtis

"Curtis"
Feb 2005
Riverside, CA

33×5×37 Posts Quote:
 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.   2020-11-12, 03:57 #8 Dr Sardonicus   Feb 2017 Nowhere 23·7·89 Posts 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.   2020-11-12, 06:30   #9
CRGreathouse

Aug 2006

3×1,993 Posts Quote:
 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: Доверяй, но проверяй.)   2020-11-12, 13:55   #10
Dr Sardonicus

Feb 2017
Nowhere

23·7·89 Posts Quote:
 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.   2020-12-02, 00:39   #11
bhelmes

Mar 2016

5438 Posts Quote:
 Originally Posted by Dr Sardonicus And I'm not sure what you're asking. Given an r for which 2*r2 - 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 ?   Last fiddled with by bhelmes on 2020-12-02 at 00:41  Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post fivemack Hardware 3 2017-10-03 03:11 henryzz Programming 3 2014-04-11 15:10 JHansen NFSNET Discussion 9 2010-06-09 19:25 CRGreathouse Msieve 8 2009-08-05 07:25 10metreh Msieve 3 2009-02-02 08:34

All times are UTC. The time now is 02:32.

Thu Oct 21 02:32:19 UTC 2021 up 89 days, 21:01, 1 user, load averages: 1.08, 1.21, 1.16