Questions tagged [factoring]
The decomposition of an integer number to the product of other integers. Algorithms such as RSA are based on the premise that no practical way has been found was to factorize large integers when they have been produced by multiplying two large primes.
356 questions
1
vote
0
answers
49
views
Impact of Known Arithmetic Progressions on Semiprime Factorization via Differences of Squares
Suppose we have known small parameters $a$, $b$, and $k$ defining two arithmetic progressions: $p = a + k i$ and $q = b + k j$, where $N = pq$ is a semiprime generated from these (with $p > q$ for $...
- 21
0
votes
0
answers
59
views
Is the large parameter k computationally significant in linear parametrizations of semiprimes with small fixed displacements?
Suppose we have a semiprime $N = p \cdot q$, where $p$ and $q$ are large primes of similar magnitude. Hypothetically, assume $N$ can be written as $N = (m \cdot k + a)(m \cdot k' + b)$, where $m$ is a ...
- 21
-1
votes
1
answer
304
views
RSA: Factorize $N$ with Cornacchia 's Algorithm . What is the computational cost of the Cornacchia's algorithm?
If we need to factor a number $N$
Given the Pythagorean quadruple (with $n$ and $m$ in $Z$)
$d=36m^2+18m+4n^2+2n+3$
$a=24mn+6m+6n+1$
$b=2(3m+n+1)(6m-2n+1)$
$c=2(3m+n+1)$
$a^2+b^2+c^2=d^2$
then if:
$N=...
3
votes
1
answer
371
views
Factor multi-prime RSA
I have a multi prime 2043 bit modulus with 8 prime factors, each 256 bit.
...
- 31
0
votes
0
answers
47
views
GNFS - square root using Fpd and CRT
I’m implementing the CRT on the “algebraic side” of GNFS (based on Briggs PDF. I have two consistent datasets: the “positive” local roots and the fully negated set. I’m trying to pin down the correct ...
- 1
6
votes
1
answer
1k
views
Factoring RSA numbers on a laptop
According to https://en.wikipedia.org/wiki/RSA_Factoring_Challenge $862$ bit $RSA$ numbers have not been factored.
With the current state of the art in sieve techniques is it possible to factor $460$ ...
- 1,215
1
vote
0
answers
144
views
Fermat's difference of squares: Expanding & factoring the subsequent differences to infinity [closed]
If I factor all subsequent differences of Fermat's difference of squares, I conclude that $(a^2-b^2) = 0$ as follows below. Did I do something incorrect in my expansion, or is my attempt at proof ...
- 101
1
vote
1
answer
107
views
Obliviously sampling RSA moduli
Is it possible to efficently sample an RSA modulus (a product of two uniformly random λ-bit primes) obliviously?
Obliviously here means that the random coins used for the sampling should not reveal ...
- 407
1
vote
0
answers
116
views
Can products of primes generated by this random walk algorithm be factored efficiently? [closed]
Algorithm Description:
A prime-generation algorithm constructs random primes by appending digits such that:
Start with a small initial digit (e.g., 1).
At each step, append a new digit d to the ...
- 577
1
vote
1
answer
140
views
Does knowing $N = AB$ and $ Q = A \oplus B$ make it any easier to factor $N$?
The title more or less sums it up. Its a trivial exercise in algebra that knowing $N = AB, Q = A+B$ makes it easy to factor $N$ (one can just directly solve the system of 2 equations in 2 unknowns to ...
- 199
3
votes
1
answer
488
views
What's wrong with the obvious reduction of factoring to DLOG?
Suppose you can solve DLOG in arbitrary groups. Then I give you the challenge of solving DLOG$(a,1)$ over the group $\mathbb{Z}_n^*$, where $a$ is some arbitrary integer and $n$ is some integer to be ...
- 1,920
2
votes
2
answers
640
views
A modified Fermat factoring algorithm to allow initial guess of $P$
Given $PQ = N$. If one was given an RSA semiprime and they could calculate a $P$ value within say $5$% of the real value of $P$ consistently, would that help in a faster method in factoring the ...
- 101
3
votes
2
answers
213
views
When is this lattice skewed after LLL reduction
Let $n,m$ be positive integers and $0 < m < n$. Construct the following knapsack-style lattice
$$L = \begin{bmatrix}
n & 0 & m^2 & 2m^3 & \cdots & (d-1)m^d \\
0 & n &...
- 260
0
votes
1
answer
190
views
How secure and convincing as authorship proof is multiplying followed by adding (plaintext×key₁ + key₂)?
Each text is a place-value representation of a number with regard to (w.r.t.) each alphabet that holds all characters in the text, in which case the number of characters in the alphabet serves as base....
- 145
0
votes
0
answers
53
views
How to factor a semiprime from a rsa key given both exponents? [duplicate]
Simple question. Let’s suppose I’ve the private exponent of a rsa key in addition to the public 1. How can I use it to factor the modulus ?
- 376