All Questions
11 questions
9
votes
3
answers
9k
views
Algorithm for detecting prime powers
While reading Peter Shor's paper Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, I came across the following quote:
"This scheme will thus work as ...
- 1,199
8
votes
2
answers
749
views
Factoring some integer in the given interval
I'm posting this question here (rather than on CSTheory) since it seems to require much more knowledge about number theory than algorithms.
Let N be a positive integer. Is there an efficient (i.e. ...
- 271
2
votes
1
answer
132
views
On an integer factoring algorithm based on smooth class number of quadratic fields
We got an algorithm and toy implementation of integer factoring algorithm
based on smooth class number of quadratic fields.
It is close to the elliptic curve factorization method (ECM) and
succeeds if ...
- 25.4k
2
votes
3
answers
1k
views
Finding integer representation as difference of two triangular numbers
Since $n = \frac{n(n+1)}{2}-\frac{n(n-1)}{2}$, every natural number can be represented as the difference of two triangular numbers:
$ n = \frac{a(a+1)}{2}-\frac{b(b-1)}{2}$. Finding such a ...
user6671
2
votes
1
answer
134
views
On a efficient algorithm for factoring bivariate polynomials modulo composite modulus assuming the solution is unique
We found and implemented in sage efficient algorithm for factoring
bivariate polynomials modulo composite modulus assuming the solution is unique up to a constant factor.
More formally let $K=\mathbb{...
- 25.4k
2
votes
1
answer
264
views
Does Coppersmith's method always finds non-trivial factor of integers of the form $n=a(2^k b+1)$ assuming $1 < a<2^k b +1$ and $b < n^{1/4-0.05}$?
Got an argument and numeric evidence that pari's implementation
of Coppersmith's method finds non trivial factor of integers
of certain form under some assumptions very efficiently.
Three $5000$ bit ...
- 25.4k
2
votes
0
answers
187
views
Factoring integers of the form $n=p q^2$ using elliptic curves
We got argument and strong experimental support
that integers of the form $n=p q^2$ can
be factored using elliptic curves easier than general integers
Q1 Is this known?
Added This is known since at ...
- 25.4k
2
votes
0
answers
110
views
Evidence of optimality of sieve algorithms
Sieve techniques apply to integer factoring and discrete logarithm to provide $2^{O(((\log n)(\log\log n)^2)^{1/3})}$ complexity for $n$ bit factoring and $n$ bit prime discrete logarithm.
The state ...
- 13.9k
1
vote
1
answer
176
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
1
vote
0
answers
29
views
Factoring semiprimes via sum of two squares? [migrated]
The following thoughts came into my head after watching Grant Sanderson's JBPM award lecture here, in which he discusses the fact that we can quickly factor 3599 by noticing it can be written as (60-1)...
- 61
0
votes
0
answers
78
views
Factoring totient of a prime
Is it any easy to factor $p-1$ when $p$ is a prime compared to general factorization problem?
What about when $2p+1$ is also a prime?
- 13.9k