mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math > Number Theory Discussion Group

Reply
 
Thread Tools
Old 2020-11-08, 17:43   #1
bhelmes
 
bhelmes's Avatar
 
Mar 2016

32·41 Posts
Default 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
bhelmes is offline   Reply With Quote
Old 2020-11-09, 14:15   #2
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

117608 Posts
Default

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).
Dr Sardonicus is offline   Reply With Quote
Old 2020-11-10, 16:14   #3
bhelmes
 
bhelmes's Avatar
 
Mar 2016

32·41 Posts
Default

Dear Dr Sardonicus



Quote:
Originally Posted by Dr Sardonicus View Post
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
bhelmes is offline   Reply With Quote
Old 2020-11-11, 10:36   #4
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

2×4,903 Posts
Default

Quote:
Originally Posted by bhelmes View Post
Red ball for putting cmd, unc, and petrw in the same paragraph!
LaurV is offline   Reply With Quote
Old 2020-11-11, 15:50   #5
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

510410 Posts
Default

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"
Dr Sardonicus is offline   Reply With Quote
Old 2020-11-12, 01:52   #6
bhelmes
 
bhelmes's Avatar
 
Mar 2016

32×41 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
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 View Post
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 View Post
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.
bhelmes is offline   Reply With Quote
Old 2020-11-12, 02:56   #7
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

5·1,013 Posts
Default

Quote:
Originally Posted by bhelmes View Post
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.
VBCurtis is offline   Reply With Quote
Old 2020-11-12, 03:57   #8
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

24×11×29 Posts
Default

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.
Dr Sardonicus is offline   Reply With Quote
Old 2020-11-12, 06:30   #9
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

135338 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
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: Доверяй, но проверяй.)
CRGreathouse is offline   Reply With Quote
Old 2020-11-12, 13:55   #10
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

510410 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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.
Dr Sardonicus is offline   Reply With Quote
Old 2020-12-02, 00:39   #11
bhelmes
 
bhelmes's Avatar
 
Mar 2016

32·41 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post

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

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Has anyone tried linear algebra on a Threadripper yet? fivemack Hardware 3 2017-10-03 03:11
Bunghole linear regression henryzz Programming 3 2014-04-11 15:10
Line sieving vs. lattice sieving JHansen NFSNET Discussion 9 2010-06-09 19:25
Linear algebra at 600% CRGreathouse Msieve 8 2009-08-05 07:25
Linear algebra crashes 10metreh Msieve 3 2009-02-02 08:34

All times are UTC. The time now is 09:13.


Sat Nov 27 09:13:08 UTC 2021 up 127 days, 3:42, 0 users, load averages: 1.29, 1.22, 1.21

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.