How much smaller can "primitive" factors be?

jshort · 2019-12-19, 17:31

When looking for "easy" to find integers $N$ that are forced to be congruent to $1 + k \cdot p$ where the congruence factor $p$ is "as large as possible" compared to $N$ , are the primitive factors of integers of the form $2^{m} + 1$ where $m$ is a "highly composite number", the best way to find these?

https://en.wikipedia.org/wiki/Highly_composite_number

PS: technical question here...….how can I combine a link (reference) into a text while I'm writing it, instead of just writing it at the bottom of my post?

R.D. Silverman · 2019-12-19, 18:23

Quote:

Originally Posted by jshort

When looking for "easy" to find integers $N$ that are forced to be congruent to $1 + k \cdot p$ where the congruence factor $p$ is "as large as possible" compared to $N$ ,

This last phrase is meaningless.

And I suggest you use standard mathematical quantifiers/notation/terminology.

Nor have you defined "easy". And your use of the variable "p" is just plain wrong. Primitive factors of 2^m+1 are 1 mod m. What do you think "p" is?

Quote:

are the primitive factors of integers of the form $2^{m} + 1$ where $m$ is a "highly composite number", the best way to find these?

Huh? You have not specified a "way to find these". In fact, you have not said
anything at all. What method did you have in mind? Saying that factors
are 1 mod m does not specify a method. Using words such as "easy", "best",
"as large as possible" is meaningless gibberish without quantifying them.

The current "best" technique for finding primitive factors consists of

(1) trial division by candidates of the form 1 + km for k < B; B is your choice depending on hardware and time constraints. Typically B = O(log^2 (2^m+1)) is
a good choice.

(1a) perhaps followed by P-1, if desired.

(2) Followed by ECM; choice of parameters depends on your goals and time constraints.

(3) Followed by NFS if time and resources permit.

Dr Sardonicus · 2019-12-19, 21:57

I'm not sure what you mean to be asking. Obviously, the smallest positive integer congruent to 1 modulo any positive integer modulus m is 1.

If you want integers whose prime factors are necessarily congruent to 1 modulo a given modulus, I repost a link to this paper which gives pertinent results about cyclotomic polynomials vis a vis "primitive factors."

If you're asking how small the value of, say, $\Phi_{n}(2)$ can be compared to $2^{n} - 1$ I don't know off hand.

If you're asking about cracking primitive parts into prime factors, I refer you to the previous response.

Dr Sardonicus · 2019-12-20, 15:13

Quote:

Originally Posted by Dr Sardonicus

<snip>
If you're asking how small the value of, say, $\Phi_{n}(2)$ can be compared to $2^{n} - 1$ I don't know off hand.

After a bit of quiet reflection on the well-known formula

$\Phi_{n}(x)\;=\;\prod_{d\mid n}(x^{d} \; - \; 1)^{\mu(\frac{n}{d})}$

I noticed that substituting x = 2 and doing a bit of rearranging gives the crude but obvious bounds

$K\cdot 2^{\varphi(n)} \; \le \; \Phi_{n}(2) \; \le \frac{1}{K}\cdot 2^{\varphi(n)}\text{ where}$

$K \; = \; \prod_{i=1}^{\infty}(1 \; - \; 2^{-i})$

K = 0.288788+, and 1/K = 3.4627466+

Substituting x = a for a > 2 gives similar bounds.

CRGreathouse · 2019-12-21, 06:51

Quote:

Originally Posted by Dr Sardonicus

$K \; = \; \prod_{i=1}^{\infty}(1 \; - \; 2^{-i})$

K = 0.288788+, and 1/K = 3.4627466+

See A048651 and A065446 for those constants in the OEIS.

Dr Sardonicus · 2019-12-21, 16:19

I find the function

$F(z) \; = \; \prod_{i=1}^{\infty}(1 \; - \; z^{i})\text{, }|z|\;<\; 1$

far more interesting than the decimal digits of its evaluation at a particular value of z. I note that

$zF^{24}(z)$

is the generating function for Ramanujan's tau function.

I also note that, using the above estimate, the question of how much smaller a primitive part of 2ⁿ - 1 can be than 2ⁿ is reduced to the question of how small $\varphi(n)$ can be as a function of n. The best you can do here is taking n to be the product of the first umpteen primes, when

$\varphi(n) \; \sim \; \frac{ne^{-\gamma}}{\log\log n}$

2019-12-19, 17:31	#1
jshort "James Short" Mar 2019 Canada 2·3² Posts	How much smaller can "primitive" factors be? When looking for "easy" to find integers $N$ that are forced to be congruent to $1 + k \cdot p$ where the congruence factor $p$ is "as large as possible" compared to $N$ , are the primitive factors of integers of the form $2^{m} + 1$ where $m$ is a "highly composite number", the best way to find these? https://en.wikipedia.org/wiki/Highly_composite_number PS: technical question here...….how can I combine a link (reference) into a text while I'm writing it, instead of just writing it at the bottom of my post? Last fiddled with by jshort on 2019-12-19 at 17:45 Reason: edit

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Aouessare-El Haddouchi-Essaaidi "test": "if Mp has no factor, it is prime!"	wildrabbitt	Miscellaneous Math	11	2015-03-06 08:17
"factors.txt.u1conflict..." files	Flatlander	Linux	3	2011-02-21 02:32
"On factors of Mersenne numbers" - Seiji Tomita	cheesehead	Math	6	2009-12-15 17:45
Would Minimizing "iterations between results file" may reveal "is not prime" earlier?	nitai1999	Software	7	2004-08-26 18:12

2019-12-19, 21:57	#3
Dr Sardonicus Feb 2017 Nowhere 2·3²·5·71 Posts	I'm not sure what you mean to be asking. Obviously, the smallest positive integer congruent to 1 modulo any positive integer modulus m is 1. If you want integers whose prime factors are necessarily congruent to 1 modulo a given modulus, I repost a link to this paper which gives pertinent results about cyclotomic polynomials vis a vis "primitive factors." If you're asking how small the value of, say, $\Phi_{n}(2)$ can be compared to $2^{n} - 1$ I don't know off hand. If you're asking about cracking primitive parts into prime factors, I refer you to the previous response.

2019-12-21, 16:19	#6
Dr Sardonicus Feb 2017 Nowhere 2·3²·5·71 Posts	I find the function $F(z) \; = \; \prod_{i=1}^{\infty}(1 \; - \; z^{i})\text{, }\|z\|\;<\; 1$ far more interesting than the decimal digits of its evaluation at a particular value of z. I note that $zF^{24}(z)$ is the generating function for Ramanujan's tau function. I also note that, using the above estimate, the question of how much smaller a primitive part of 2ⁿ - 1 can be than 2ⁿ is reduced to the question of how small $\varphi(n)$ can be as a function of n. The best you can do here is taking n to be the product of the first umpteen primes, when $\varphi(n) \; \sim \; \frac{ne^{-\gamma}}{\log\log n}$