Factorization is the problem of taking an integer and finding the set of prime numbers that produce the integer when multiplied together. For large integers with large factors, factorization is hard and is the basis for cryptosystems like RSA.

learn more… | top users | synonyms

3
votes
0answers
54 views

How does the Number Field Sieve find the target number for Diffie-Hellman?

I have read some papers relating to the Number Field Sieve, but I could not figure out how this algorithm helps in Logjam, or even what is meant by the number field. What is this? What is meant by ...
3
votes
0answers
56 views

Blinding to mask private key operations

Blinding is often used to mask private key operations when the underlying problem is integer factorization. For example, its used in both RSA and Rabin-Williams signature schemes. This presumes ...
3
votes
0answers
148 views

Relations between RSA and DLOG, factoring and DLOG

Definition: (The generalized Diffie-Hellman problem) Let $n=pq$ for two large primes $p,q$. Given $x, x^a, x^b,n$, find $x^{ab}\pmod{n}$. (1) Is there a known reduction from the GDH problem to ...
3
votes
0answers
118 views

What role plays Quantum Fourier Transformation in Shor's integer factorization algorithm?

I cannot seem to understand the role or goal of Quantum Fourier Transformation in Shor's integer factorization algorithm. Is it used to collapse all quantum states into one, in which it has a factor ...
3
votes
0answers
123 views

RSA security assumptions - does breaking the DLP also break RSA? [duplicate]

Possible Duplicate: Would the ability to efficiently find Discrete Logs have any impact on the security of RSA? I'm wondering if breaking the DLP, that is the basis for ElGamal and DSA, would ...
2
votes
3answers
314 views

Is it possible to attack RSA with a WalkSat derivative?

We consider a large $n$-bit number $N$. We want to find a factor, if it admits any. For $m$ taking values from $1$ to $n$, perform the following three steps (actually, for each $m$, perform many ...
2
votes
1answer
342 views

Elliptic Curve Factorization: Why are elliptic curves suited for this kind of task?

Currently I'm working on a presentation of a paper that talks about the factorization of large numbers. In the paper elliptic curves are presented as a way to factorize large numbers. After hearing a ...
2
votes
1answer
269 views

How did they factor RSA-704?

I don't understand the 'Wiedemann algorithm' works. Can someone explain the factoring of RSA-704 in an easy way?
2
votes
2answers
191 views

How can I factorize a 350 bit (106 decimal digits) number in two prime factors?

I have this large number: 1728098743723095094470726818328193358068864405124007684733613106475812450278961107574624070107782941006379 which is the multiplication of two unknown large prime numbers. I ...
2
votes
1answer
624 views

Why should the primes used in RSA be distinct?

The two primes $p$ and $q$ part of the public key need to be distinct. What's the reason for them to be distinct? Is it because factorization of $p^2$ where $p$ is a prime is relatively easier, or is ...
2
votes
1answer
341 views

Attack for RSA 1024 bit with Low Public Exponent

I am facing a challenge at university. Our teacher give us the challenge to try to break an RSA 1024 bit. We have public modulus N and public exponent e (0x03), we don't know the padding. We have a ...
2
votes
1answer
153 views

What's the strategy for future directions in cryptography? Bigger numbers/faster searching, or new methods, say, of factoring?

I'm taking a course in cryptography, and I would value any comments. This is not too technical a question, but more about directions or strategy in cryptography. My question is, is public key ...
2
votes
1answer
159 views

Prime factorization of 700 decimal digits number

I'm a newbie to encryption. If I create a number 'n' as a product of two prime numbers 'p' and 'q' with the following specifications: 'p' is a fully random prime with 300 decimal digits in length. 'q'...
2
votes
2answers
100 views

RSA and difference between factors

As I understand, for RSA $n = p \cdot q$. For the key to be safe enough from getting factored, $p$ and $q$ have to be far from each other. How far do they have to be? For example, if I have two $1024$-...
2
votes
2answers
176 views

Does it necessarily mean that an RSA moduli generated with poor randomness is not random?

In 2012 a group of researchers collected a large amount of RSA moduli and calculated their greatest common divisor in order to find common factors between them. By finding a common factor they could ...
2
votes
1answer
68 views

Understanding the Hidden Subgroup Problem specific to Integer Factorization

I've been reading about the Hidden Subgroup Problem (HSP), specifically trying to understand how it is related to the integer factorization problem. I've read What exactly is the impact of the hidden ...
2
votes
3answers
131 views

Can spatial filters be used to factor composite numbers?

$Z=(N-XY)^2$ is a surface with absolute minima ($0s$) anywere $Y=N/X$. I know this question is naiive, but shouldn't it be possible to apply a lossy compression filter to this function which ...
2
votes
1answer
342 views

Square roots, prime factorization

I´m stuck in my homework and since its homework, I would rather get some hints than full solution. The problem goes: factorize n = 88416763 in case that you know that the square roots of 51733469 (...
2
votes
1answer
352 views

Choosing good parameter for Lenstra's elliptic curve factorization

In Wikipedia, there is an article explaining Lenstra's factorization algorithm. As far as I got it, we choose some $e \in \mathbb{N}$ and a point $P$ on the curve and then calculate $eP$. While ...
2
votes
2answers
1k views

Optimising Pollard's Rho algorithm for large semi-primes

I have programmed an implementation of Pollard's Rho factoring algorithm using C++ and the GMP library. It is reasonably fast with large numbers, however I haven't implemented any form of cycle ...
2
votes
1answer
181 views

Discrete log analog of ECM factoring algorithm?

Anecdotally, most factoring algorithms have a corresponding variant algorithm that can be used to attack the discrete log problem using similar ideas. Is there an analog of the elliptic curve (ECM) ...
2
votes
2answers
12k views

OTP from Sony BIOS password recover [closed]

From Dogbert's blog: Sony has a line of laptops ("Vaio") which compete mainly in the high value market segments. They implemented a master password bypass which is rather sane in comparison to the ...
2
votes
0answers
59 views

Are analog quantum computers a threat to RSA and DLP?

We already know that D-WAVE's "quantum computers" can't really run the Shor's algorithm, because the way they're built doesn't qualify them as universal quantum computers. Now researchers actually ...
2
votes
0answers
26 views

Are there UFDs where the factorization problem is difficult but finding irreducibles is cheap?

Factorization of integers is hard, but finding irreducibles is expensive. Is there a ring where factorization is assumed hard but finding irreducibles is much cheaper than over $\Bbb Z$? It could ...
1
vote
1answer
173 views

Why is factoring $p-1$ easy when $p$ is a safe prime?

A paper states: [...] $(p,g,y)$ is a correct ElGamal public key if $g^x=y\pmod p$. To verify this the order of $g$, and thus the factorization of $p-1$, is needed. This is easy for safe primes (i....
1
vote
2answers
638 views

Is there an algorithm for factoring N, which is just as simple as this one, but faster?

I found a simple algorithm for factoring semiprime numbers, you can read about it in Factoring Semiprimes and Possible Implications for RSA. It basically works like this: You reverse the digits in $...
1
vote
2answers
288 views

Factors of RSA modulus

In the article A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, the original RSA article, it is mentioned that Miller has shown that n (the modulus) can be factored using any ...
1
vote
1answer
172 views

Brute force RSA cracking

Suppose one had a complete list of primes up to $2^{n+1}-1$. Then wouldn't one be able to crack an $n$-bit RSA public key in time $O(\pi(2^{n+1}-1))$, making RSA insecure? Thanks, René
1
vote
1answer
58 views

What is the advantage of Pseudosquare?

Pseudosquares ,which are not square but Jacobi symbol are still 1, are used in some cryptographic algorithm. What is the advantage of them over the exact squares? If we used squares instead of ...
1
vote
1answer
62 views

Computational Diffie-Hellman problem over the group of quadratic residues

Suppose that $N=pq$ where $p$ and $q$ are safe primes. $\mathbb{QR}_N$ is the group of quadratic residues which is a cyclic group with order $\frac{\phi(N)}{4}$. Let $g$ be the generator of $\mathbb{...
1
vote
2answers
152 views

Factoring large $N$ given oracle to find square roots modulo $N$

When $p$ and $q$ are distinct odd primes and $N = pq$, the points in $\mathbb Z_N^\ast$ have either zero or four square roots. A quarter of the points have four square roots; the rest have no square ...
1
vote
1answer
296 views

Compare two approaches for cracking RSA key

I came across these questions while studying for a crypto course, does anyone have any ideas on how to answer these? (a) Random prime numbers of size 1536 bits are chosen to generate an RSA modulus ...
1
vote
1answer
62 views

Factorization of RSA modulus using a qubic residue

Suppose that someone uses RSA with $n = pq$, exponent $3$, also $3$ divides $\varphi(n) = (p-1)(q-1)$ and $2$ different roots $y$ and $z$ of the equation: $$x \equiv c \ (mod \ n)$$ are known (for ...
1
vote
1answer
81 views

Sieving the sequence $x^2-n$ to recognize b-smooth numbers

I am currently programming the quadratic sieve and have several literature books / papers and will take an example out of [1] for my question: [1] An Introduction to Mathemtaical Cryptography by J. ...
1
vote
3answers
293 views

Programming language for modular arithmetic over large numbers [closed]

I'am trying to implement algorithms on integer factorization.This involves dealing with integers of 200-500 digits and doing modular arithmetic over them.Which programming language has inbuilt support ...
1
vote
1answer
251 views

Relationship between Elliptic Curve Discrete Log, Integer Discrete Log, and Integer Factorization

I am trying to look into a relation between the following three problems which are widely used to build public crypto systems: Integer Discrete log Elliptic Curve Discrete log Integer Factorization ...
1
vote
1answer
2k views

Reduction of Integer factorization to Discrete logarithm problem

I was reading Eric Bach paper entitles "Discrete logarithms and factoring", in which he states the following reductions: solving the integer factorization problem suffices to solve the discrete ...
1
vote
1answer
91 views

Time complexity of trial division

Suppose $n=pq$, where p,q are prime numbers. let $p ( \le q)$ be the smallest prime, then we know that $p \le \sqrt{n}$. In trail division, we check $n \mod i$ for the values of $i$ from 2 to $\...
1
vote
1answer
69 views

Factors of the group order to secure against Pohlig-Hellman

I am looking into the security of Diffie-Hellman and the discrete log in general. To make sure an attacker can not use Pohlig-Hellman to solve the discrete log quickly we need to make sure that the ...
1
vote
1answer
82 views

If someone had a list of all primes, would it be possible for them to factor any integer in polynomial time? [duplicate]

For example, if they somehow got a function that would churn out any arbitrary amount of primes in a row. Could they break the RSA problem then?
1
vote
1answer
73 views

How to choose the integer m in the general number field sieve (GNFS)?

Given an integer you want to factor $N$, GNFS starts by selecting a monic irreducible polynomial $f \in \mathbb{Z}[X]$ and an integer $m$ such that $f(m) \equiv 0 \text{ mod } N$. In practice, if $m$ ...
1
vote
1answer
109 views

What is the value of Q such that Q|P-1 where P is a prime number?

For my crypto assignment, I'm asked to enter a prime P and generate Q such that Q|P-1 Can anyone guide me what is Q|P-1?
1
vote
1answer
781 views

Discrete log problem with modulus prime

I am a bit confused on the hardness of the discrete logarithm problem. Does it become intractale only when it is mod n, where n is a large composite number (Like RSA key). What about if it is mod a ...
1
vote
1answer
157 views

Security relevance of random factor in Paillier

In the Paillier cryptosystem [1] the encryption of $m \in \mathbb{Z}_N$ with randomness $r \in \mathbb{Z}_n^*$ is $c = g^m r^n \bmod{n^2}$. The additive-homomorphic property of the system shows that $...
1
vote
0answers
72 views

Zero knowledge of two factor

Here I overconfident in myself state that I can show, that n has two factors. This is not completely true, can possibly show $n$ is composite - prover generates RSA key with modulo $n$, and gives $e$ ...
1
vote
0answers
79 views

Is the half-homomorphic property of RSA a problem for blind RSA signatures?

For blind RSA signatures, is it problematic that RSA is half-homomorph? Take a scenario where blind RSA signatures are used for something like a voting procedure or this proposal: Lots of people, ...
1
vote
0answers
139 views

Determine the iteration times using Pollard's rho Method for factoring

Let's say, we have a large number $n=181937053$ and $f(x)=x^2+1$. And also we know that $n=12391 \times 14683$. The problem is that ,using Pollard rho method, can we find the algorithm iteration ...
1
vote
0answers
180 views

Distributed integer factorization?

I'm looking around for publicly published work on factorization of large numbers using distributed systems of any kind. So far I've come across the PDF "Mapreduce for integer factorization" by Javier ...
1
vote
0answers
74 views

Why is it impractical to generate a semiprime dictionary? [duplicate]

This might be a very simple question. However, I am just learning the concept, so just excuse me. I am wondering why there is not any attempt to generate all semiprime numbers? (as an dict. attack to ...
1
vote
0answers
62 views

Generating Polynomials for the MPQS

I'm going to try and eventually factor RSA-100, but my current QS needs a lot of improvement, so I'm going to try and switch over to the MPQS. I'm a bit confused as to how the MPQS works, which is ...