All Questions
Tagged with prime-factorization sieve-theory
18
questions
1
vote
0
answers
82
views
Is the quadratic sieve algorithm on Wikipedia wrong/inefficient?
I'm confused by a few aspects of the algorithm.
https://en.wikipedia.org/wiki/Quadratic_sieve
First, I'm confused by the choice of $a_i$'s.
For each iteration:
Choose $x \in \{ 0, \pm 1, \pm 2, \...
- 21
1
vote
0
answers
57
views
A question on primes larger than a bound in an arithmetic progression
Let $n \in \mathbb{Z}$ be a semi-prime with unknown factorization, $n = pq$, where $p, q \in \mathbb{P}$, the set of primes. Without loss of generality, let $p \lt q$.
Say we have done trial division ...
- 3,341
0
votes
1
answer
114
views
What is the most efficient way to compute sum of sum of divisors of all numbers from 1 to n?
$σ_1(i)$ be the sum of divisors of $i$,
Calculate
$S(n) = \sum_{i=1}^n σ_1(i)$
I am looking for something better than $O(\sqrt{n})$
To address @ingix's question here is my $O(\sqrt{n})$ python ...
- 491
2
votes
1
answer
159
views
The sieving stage in quadratic sieve algorithm
I've been trying to figure out how sieving works in the quadratic sieve factorization algorithm.
Example: to factorize 90283. The ceil of the square root of 90283 is 301. We generate a sequence $x^{2}$...
- 55
1
vote
0
answers
39
views
Factor the Outputs of a Quadratic using Sieving
I want to factor $(n-1)^3+1$ for many values of $n$. Meaning, for every value of $n$ from $1$ to $N$ for some large $N$ I want a list of prime factors and corresponding powers for $(n-1)^3+1$. We ...
- 779
6
votes
2
answers
1k
views
Sieve of Eratosthenes : why can we stop at the $\sqrt n$? [duplicate]
The sieve of Eratosthenes is an algorithm to calculate all the primes up to $n$.
It works by iterating $i$ from $1$ to $n$, and at each time strikes out the multiples of $i$.
In many optimizations, I'...
1
vote
0
answers
38
views
Help regarding Quadratic Sieve
I'm working on a code that recovers/retraces the prime no's from which a 30-digit number was formed. As, this is a factorization problem I have started regarding various algorithms about it. This ...
- 11
3
votes
0
answers
157
views
Generating prime p where p-1 is hard to factor
This paper: An Interactive Identification Scheme Based on Discrete Logarithms and Factoring requires generating primes $p$ with the following special format:
We choose $p$ with the property that $p ...
- 3,331
0
votes
0
answers
63
views
Resource for Using Logs in Quadratic Sieve Sieving.
I am trying to implement the Quadratic Sieve as fast as possible without parallelization or Multiple Polynomial. Through some reading, it seems to me that using logarithms for the sieving step is the ...
2
votes
0
answers
323
views
Find minimum GCD of a pair of elements in an array
Given an list of elements, I have to find the MINIMUM GCD possible
between any two pairs of the array in least time complexity.
Example
Input
list=[7,3,14,9,6]
...
- 21
1
vote
1
answer
270
views
In the rational Sieve method why does n = gcd(a-b,n)×gcd(a+b,n) exactly?
As a quick notation explanation of the basic rational sieve method, a set of primes $P$ that are coprime to a number $n$ tested for primality are chosen randomly as follows(from wikipedia):
Suppose ...
- 1,171
7
votes
2
answers
3k
views
How exactly does wheel factorization work and what is it used for?
I would like to learn how to use wheel factorization but am having trouble understanding it. I tried reading the wikipedia article but found it confusing (even the talk page says it's a mess). What ...
- 449
2
votes
0
answers
273
views
In the General Number Field Sieve, can we estimate the size of the matrix in terms of the number being factored?
One of the last steps of GNFS is to solve a large matrix-vector equation (usually using the Block Lanczos algorithm or the Block Wiedemann algorithm). The matrix for the most recent RSA number ...
- 1,068
1
vote
2
answers
1k
views
Finding Prime Factors of a number in $\log(n)$
Only Strategy I am aware of for finding factors efficiently is sieve of eratosthenes but from sieve I first have to pre-compute the prime numbers less than than $\sqrt{n}$. I want to skip this ...
- 43
8
votes
7
answers
3k
views
Sieve of Eratosthenes : why $\sqrt n$ work?
I have a question about Sieve of Eratosthenes,
I refer at the "simply version" :
If I have an $\boldsymbol{n}$ and I want the prime numbers up to n,
I search and delete multiply up to $ \...
- 103