All Questions
13 questions
1
vote
1
answer
178
views
+50
On a probabilistic integer factorization algorithm given bounds for one prime factor
We got a probabilistic integer factorization algorithm and experimental evidence with large
integers given bounds for one factor.
Let $D \ge 2$ be real number and let $p,q$ be primes and $N=pq$.
...
- 25.4k
6
votes
2
answers
804
views
Must Mersenne numbers be divisible by arbitrary large primes with exponent one?
Let $M_n$ denote the Mersenne numbers $M_n=2^n-1$.
As $n$ varies, must $M_n$ be divisible by arbitrary large prime $p$
with exponent one, i.e. $p \mid M_n, p^2 \nmid M_n$?
In other words, must the ...
- 44.4k
3
votes
3
answers
382
views
Closed formula for number of ones in a proper factor tree
Edit [2023 Dec 7]: One of my specific wonders, along with that of students, is around when a recursive formula might have – or be expected to have – an explicit or closed formula. What is the ...
- 50.8k
2
votes
0
answers
140
views
Integers with exactly three factor pairs whose successors are relatively prime
I am interested in the following problem, and will appreciate pointers around how it can be solved – partially or fully – and/or indicators around whether it is even tractable:
Characterize $N \in \...
- 7,831
0
votes
0
answers
138
views
A diophantine equation involving partial sums of exponentials similar than the equation in Fermat's Last Theorem
I'm curious about the following diophantine equation from my invention: I don't know if this is in the literature, I wrote it using creativity in an attempt to write a variant of the equation in ...
3
votes
1
answer
137
views
Subexponential algorithms that apply only one of factoring and discrete logarithm?
Shor (quantum polynomial), Number Field Sieve (subexponential), Pollard rho (square root) all have both factoring and discrete logarithm over $\mathbb F_p^*$ variants.
What are the subexponential ...
- 879
4
votes
1
answer
288
views
Is total degree version and $x,y$ degree version of Coppersmith's theorem correct?
The notes here https://web.eecs.umich.edu/~cpeikert/lic13/lec04.pdf have the note 'Small decryption exponent $d$: so far the best known attack recovers $d$ if it is less than $N^{.292}$. This uses a ...
- 218
7
votes
1
answer
382
views
$\log \log p / \log \log n$, where $p|n$, gets equidistributed in [0,1] (for almost all $n$)
According to Hardy-Ramanujan/Erdős-Kac we know that usually there are $\sim\log\log n$ prime numbers in a factorization. But if you pick up a natural number at random, and you factor it, what is the ...
- 105k
2
votes
1
answer
450
views
Is there a "small $\omega$" number theorem?
In my studies of how primes jump (search this forum for a link), a question has been raised which may have been studied. Can anyone jump-start my literature search with references regarding the ...
5
votes
1
answer
214
views
Dynamics of the distribution of prime factorization types in increasing intervals
I've tagged this as reference request as surely this question must be very well investigated, I just don't know how to look for it. Most likely the perfect answer will be in form of a keyword for ...
- 43.7k
9
votes
2
answers
1k
views
runs of consecutive non squarefree integers
This question gained no attention at Math SE.
Call a sequence of $k$ consecutive naturals squary if each one of them is divided by a square > 1. The Chinese Remainder theorem trivially guarantees us ...
CommunityBot
- 1
6
votes
1
answer
1k
views
Using the decomposition $641 = 5^4 + 2^4$ to factor $F_5$
The question in the title arises from a problem in Stewart's "Galois Theory, Third Edition" (and possibly elsewhere) which has been bugging me for a few days since reading it:
Problem 19.5 (p. 224) ...
- 16.5k
9
votes
3
answers
980
views
$\omega(p^n - 1)$ as $n \rightarrow \infty$
Although I am also interested in the number of distinct prime factors (not counting
multiplicity), today I use $\omega(m)$ to denote the number of (positive) prime
factors (with multiplicity) of the ...
- 61.9k