Questions tagged [prime-factorization]
For questions about factoring elements of rings into primes, or about the specific case of factoring natural numbers into primes.
2,081
questions
2
votes
2
answers
262
views
Prime factors of $5^n+6^n+7^n+8^n+9^n+10^n$
I currently run an integer factoring project of the numbers of the form $$5^n+6^n+7^n+8^n+9^n+10^n$$ where $n$ is a non-negative integer.
Do the prime factors have a particular form as it is the case ...
- 85.1k
0
votes
0
answers
52
views
Found a relation regarding the primes, is this interesting?
Define $S_{odd}$ as all $n\in N $ where $n$ is the product of an odd number of distinct primes. Define $S_{even}$ similarly. Thus:
$$S_{odd} = \{2,3,5,...,30,42,....\}$$
$$S_{even} = \{6,10,14, ....,...
- 702
-1
votes
1
answer
84
views
Dottie number and prime factorization
It's related to Dottie number and prime factorization .
Let :
$D=\operatorname{Dottie-number}\simeq 0.7390851332$
Now define $n\geq 3$ an integer:
$$\lfloor\left(D\right)^{-2n}\rfloor=P$$
Then it ...
2
votes
1
answer
96
views
Is $\omega(n)=16$ the maximum?
What is the largest possible value of $\omega(n)$ (the number of distinct prime factors of $n$) , if $n$ is a $30$-digit number containing only zeros and ones in the decimal expansion.
I checked ...
- 85.1k
0
votes
0
answers
55
views
Ramification of primes on $\overline{\mathbb Q}$
My concern arises about the existence of unramified primes in infinite extensions of $\mathbb Q$, particularly in $\overline{\mathbb Q}$.
Now, in general there exist be a definition of ramification ...
3
votes
1
answer
308
views
Center Binomial can "Self-Factor" RSA semiprimes. [closed]
Given two odd primes $P$ and $Q$ s.t. $P < Q$, $PQ = N$, $P \neq 3$ and $Q \neq 5$ at same time... the center binomial $f(k)=\frac{(2k)!}{(k!)^{2}}$ can be used to factor $N$. This will not be ...
- 129
1
vote
2
answers
90
views
SemiPrime Test to determine distance between P and Q
I have two composite primes (semiprimes) where $17*641 = 10897$ and $101*107 = 10807$.
Notice that $10897$ and $10807$ are almost equal. Their square roots are $104.38$ and $103.95$ respectively. But ...
- 129
0
votes
0
answers
59
views
Why trial division algorithm to find the prime factors of $N$ is $O(\sqrt{N})$, even though you need to check after $\sqrt{N}$?
I have understood that to check if $N$ is prime, it is enough to check up to $\sqrt{N}$ because if it has divisor up to that point then it's composite number. However, if you want to count all the ...
- 21
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
0
votes
3
answers
471
views
Is this algorithm efficient as a factorization algorithm?
Let $N=8*G+3$ $->$ $N=(4*x+2)^2-(2*y-1)^2=p*q$ with $q/p < 2$
Given this system if we choose $D^2$ odd close to $8*x+4$
$->$ $(8*x+4-D^2)=W*V$ with $V$ and $W$ odd very close to each other
...
0
votes
0
answers
31
views
Form of the divisors of a number (Prime Factorization). Is this algorithm-based proof correct? [duplicate]
I am trying to proof the following result:
For a number $n$ whose prime number decomposition is $p_1^{\alpha _1} ... p_m^{\alpha _m}$. Every divisor of $n$ has the form $p_1^{\beta _1} ... p_m^{\beta ...
- 1,231
0
votes
1
answer
59
views
ways to write out a number in exponential form
Let's say that we have a number of the form $n^n$.
How many integer pairs of the form $a^b$ are equivalent to this number?
for example, let's say that $n=8$
We have $2^{24}$, $(-2)^{24}$, $4^{12}$, $(-...
- 342
-2
votes
1
answer
67
views
All possible factorisations of a number
Is there a method for finding all possible n-factor factorisations of a number? For example, if all possible 2-factor factorisations of 90 (up to order) are:
1 × 90
2 × 45
3 × 30
5 × 18
6 × 15
9 × 10
...
- 37
1
vote
1
answer
110
views
Open Question: For natural $n$ with prime decomposition $\prod p_i^{r_i}$, define $f(n)=\sum p_i r_i$. Find all $n$ such that $f(n)-f(n+1)=1$.
A question I created myself:
For any $n\in \Bbb{N}$, we can get $n = p_1^{r_1}\cdots p_m^{r_m}$, where $p_i$ are primes. Take $$f(n)=p_1r_1+\cdots+p_mr_m$$
Find all $n$ such that $f(n)-f(n+1)=1$
It ...
- 27
0
votes
0
answers
70
views
Show for some n Fermat’s method is faster than reverse trial division
One way to find a nontrivial
divisor of n is Fermat’s factorization method:
Suppose that we have an odd number n > 1 which we know is
composite and not a perfect square.
Calculate $\lfloor \sqrt{n}...
- 254