All Questions
18
questions
1
vote
0
answers
535
views
B-Smooth Number Generation
A number is defined as being $B-Smooth$ if none of its prime factors are greater than the value of $B$. For example, $105$ is $7-Smooth$, because $105=3\cdot5\cdot7$.
Given a number $B$, how could you ...
- 442
1
vote
0
answers
57
views
Find number in interval with small prime factors
Given two natural numbers A and B where A + 1 < B, and a prime number ...
- 305
1
vote
2
answers
79
views
Easy ways of finding small prime divisors
Are there any "relatively simple" ways of seeing whether a number is divisible by a small prime not 3. For example, one simply sums the digits of n modulo 3 and if they sum to zero, then n is ...
- 344
2
votes
1
answer
286
views
Algorithm that returns the number of prime factors (non-distinct) of an integer WITHOUT finding the prime factorization
Currently, the most efficient algorithm that classical computers can use to factor large composite numbers is the General Number Field Sieve (GNFS), which runs in subexponential time. It returns a set ...
- 145
1
vote
0
answers
801
views
number of coprimes to a less than b
We know that number of coprimes less than a number can be found using euler function https://brilliant.org/wiki/eulers-totient-function/ But if there are two numbers p,q and we need to find number of ...
- 139
2
votes
1
answer
2k
views
Semiprime factorization
I was thinking about semiprime factorization, and I had an idea of an algorithm:
Let's take a small semiprime for this example: 3053. So we have to primes ...
- 21
0
votes
1
answer
156
views
Quality of prime seeking methods
I am working on prime numbers with emphasis of prime search heuristics, and found the probabilistic methods for primes seeking, I am looking for a review of those methods quality in terms of machine ...
- 109
2
votes
0
answers
177
views
How to find the smallest number exceeding $n$ with at least $m$ prime factors
I'm wondering if there is a clever way to find the next number containing at least $m$ prime factors (not necessarily distinct) after a given number $n = p_1 \dots p_{m+k}$ given with prime factors.
...
- 1,275
5
votes
3
answers
3k
views
What would a polynomial time algorithm for prime factorization do?
I'm not a mathematician by trade so I apologise if this is a dim question. I realise that no such algorithm currently exists but I'm trying to understand what such a polynomial time prime ...
1
vote
1
answer
646
views
Lower bounds for integer factorization
Suppose we know that $n=p_a p_b$ where $a<b$ and $n$ are known integers and $p_a$ is the $a$-th prime. ( For example $n = p_{102} \cdot p_{2034}$). Then the time $t(n)$ to factor $n$ is greater ...
user276611
1
vote
1
answer
340
views
Fermat's factorization algorithm
I'm looking at the following problem. I know the basic algorithm, but to be honest, I'm kind of lost on how to solve part (a). I think I've solved (b) and (c) based on what the problem says and my ...
- 521
10
votes
3
answers
758
views
What is the most efficient algorithm for factorisation when an approximate value of one factor is known
If I am given the following number:
1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350
692006139
And am told that one of ...
3
votes
3
answers
1k
views
Finding the prime number $n$: why checking for a divisor between 2 and $\lfloor \frac{n}{2} \rfloor$ is enough?
Let's say I want to check whether 33 (say $n$) is a prime number or not. Instead of checking whether 33 is divisible by a number between 2 and 31 or not, it is sufficient enough to verify that 33 is ...
- 301
1
vote
0
answers
401
views
Efficient way to find primitive root without prime factorization
I was wondering if there is a more efficient brute-forcing approach to find any primitive root of number $p$ without prime factorization.
My approach is as follows:
Get a random residue class $[x]$ ...
- 11
1
vote
2
answers
362
views
Finding the upper bound for a number's factors length
Okay, so the title is a bit misleading but I had to keep it short.. Anyhow, if I have a number X what will the length of it's longest two factors be?
For example:
$X = 10000$
I want $3$ and $3$ (...
- 353