20201108, 17:43  #1 
Mar 2016
304_{10} 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*98011 =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 20201108 at 17:44 
20201109, 14:15  #2 
Feb 2017
Nowhere
2^{2}×5×7×31 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*r^{2}  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 PariGP command sqrt(Mod(1/2, p)) will return Mod(r, p) for the r in the interval (0, p/2). The PariGP 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). 
20201110, 16:14  #3  
Mar 2016
2^{4}×19 Posts 
Dear Dr Sardonicus
Quote:
The first prime p concerning the polynomial f(n)=2n²1 (with pf(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%5E21.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 

20201111, 10:36  #4 
Romulan Interpreter
Jun 2011
Thailand
9275_{10} Posts 

20201111, 15:50  #5 
Feb 2017
Nowhere
4340_{10} 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 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, 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] Last fiddled with by Dr Sardonicus on 20201112 at 00:45 Reason: Add "has two distinct prime factors" 
20201112, 01:52  #6  
Mar 2016
2^{4}×19 Posts 
Quote:
Exact right Quote:
I am trying to parallize the algorithm and to improve the runtime. Quote:
I think I can be sure that in this case m>n_max. Therefore I can sieve out the primes with pf(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. 

20201112, 02:56  #7 
"Curtis"
Feb 2005
Riverside, CA
5^{2}×11×17 Posts 
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.

20201112, 03:57  #8 
Feb 2017
Nowhere
2^{2}×5×7×31 Posts 
I note OEIS A005528, Størmer numbers or arccotangent 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. 
20201112, 06:30  #9 
Aug 2006
1011101010110_{2} Posts 
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: Доверяй, но проверяй.)

20201112, 13:55  #10  
Feb 2017
Nowhere
2^{2}×5×7×31 Posts 
Quote:
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. 

20201202, 00:39  #11  
Mar 2016
2^{4}·19 Posts 
Quote:
(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 20201202 at 00:41 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Has anyone tried linear algebra on a Threadripper yet?  fivemack  Hardware  3  20171003 03:11 
Bunghole linear regression  henryzz  Programming  3  20140411 15:10 
Line sieving vs. lattice sieving  JHansen  NFSNET Discussion  9  20100609 19:25 
Linear algebra at 600%  CRGreathouse  Msieve  8  20090805 07:25 
Linear algebra crashes  10metreh  Msieve  3  20090202 08:34 