1
vote
1answer
35 views

Any simpler way to do Pollard's p-1 method?

I found calculating factorization by Pollard's p-1 method is almost impossible if use a conventional scientific calculator. For example, I am trying to factor ...
1
vote
1answer
28 views

Probability Distribution of Count of Factors for All Numbers

Is the following a known thing? Define "factor count" as the count of factors each number has, then subtract 1. Ignore the number "1" as a factor. For example: Prime numbers have a factor count ...
1
vote
2answers
88 views

Isomorphism between Rings $\mathbb{Z}[\frac{u}{v}]$ and $\mathbb{Z}[\frac{1}{v}]$, u,v relatively prime

Let $u$ and $v$ be relatively prime integers, and let $R'$ be the ring obtained from $\mathbb{Z}$ by adjoining an element $\alpha$ with the relation $v\alpha=u$. Prove that $R'$ is isomorphic to ...
2
votes
2answers
89 views

Unique number of numbers multiplied together

I'm sure this has been asked before, but how many unique numbers can be made from multiplying $4$ numbers, each between $1$ and $100$? My guess is the all numbers from $1$ to $100^4$ except those ...
2
votes
0answers
68 views

Probability distribution of the (size of the) smallest prime factor

Related question: Expected smallest prime factor Background: Given a toolbox of factorization algorithms (like trial division, ECM, quadratic sieve, GNFS) and a set of large composite numbers, I'm ...
1
vote
2answers
152 views

Prime factorization: easiest way?

For prime factorization, is there another way of doing it, distinct from dividing the number by a series of primes (starting by the smallest)? Couldn't we also pick the same series of primes and ...
0
votes
2answers
90 views

Intermediate Problem Solving Patterns involving Prime Factoring

a and b are positive integers such that $a\times b= 500000000,$ where neither a nor b contain any zeros. Find a and b where $a<b.$
0
votes
1answer
57 views

If n > 3 and (n + 1) is a square, is there any n that is a prime?

I am looking at properties of squares and came about this property. I am investigating the difference of squares in relation to primes.
1
vote
1answer
34 views

show that if $m,n\in\mathbb{N}$ are such that $(m,n)=1$, then $\frac{(m+n-1)!}{m!n!}\in\mathbb{N}.$

show that if $m,n\in\mathbb{N}$ are such that $(m,n)=1$, then $$\frac{(m+n-1)!}{m!n!}\in\mathbb{N}.$$ I have a theorem (shown in my text) that says $$\fbox{If $a_1,...,a_m\in\mathbb{N}^*$ then ...
0
votes
2answers
81 views

Computing p and q from private key

We are given n (public modulus) where $n=pq$ and $e$ (encryption exponent) using RSA. Then I was able to crack the private key $d$, using Wieners attack. So now, I have $(n,e,d)$. My question: is ...
2
votes
1answer
83 views

Unexpected data for primes?

I found some unexpected data for primes. Consider $p(n)$ being the product over all primes smaller than or equal to $n$. When factoring $p(n)^a +1$ for $a=1$ or $a=2$ we get the expected amount of ...
14
votes
9answers
2k views

Is $83^{27} +1 $ a prime number?

I'm having problems with exercises on proving whether or not a given number is prime. Is $83^{27} + 1$ prime?
2
votes
2answers
307 views

Primality test square root of n

I was reading about primality test and at the wikipedia page it said that we just have to test the divisors of $n$ from $2$ to $\sqrt n$, but look at this number: $$7551935939 = 35099 \cdot 215161$$ ...
3
votes
4answers
174 views

I found out that $p^n$ only has the factors ${p^{n-1}, p^{n-2}, \ldots p^0=1}$, is there a reason why?

So I've known this for a while, and only finally thought to ask about it.. so, any prime number ($p$) to a power $n$ has the factors $\{p^{n-1},\ p^{n-2},\ ...\ p^1,\ p^0 = 1\}$ So, e.g., $5^4 = ...
1
vote
1answer
61 views

Divisibility and factors [duplicate]

1) Can factors be negative? Please prove your opinion. 2)If prime factorization is given to you, how will you find out how many composite factors are there? Not the factors, just how many. For 2), my ...
4
votes
2answers
74 views

A set of numbers where none can be made by multiplying others in the set.

(I'm a programmer, please excuse my abuse of or lack of proper mathematical language) The other day I needed to find a natural number that is cleanly divisible by all integers in the range ...
1
vote
2answers
489 views

Number of proper divisors generally prime

If we count the number of proper divisors of a positive integer, why do we usually get a prime number (or $1$)? ...
2
votes
4answers
119 views

Is 440 a factor of 72840?

I would like to know how to solve the following question: Is 440 a factor of 72840? I would have thought that this involves dividing 72840 by 440 and seeing if it produces an integer. However, the ...
0
votes
1answer
21 views

What is the pair $(n,k)$ called where $n$ is an integer and $k$ is the ordered factorization index?

I’m developing a number class (as in Object-Oriented Programming) and am wondering what to call it. At its core, it represents an integer, but in a way in which not all integers are unique. What it ...
4
votes
1answer
149 views

How to implement birthday paradox continuation of elliptic curve factorization algorithm

I have already implemented Lenstra's algorithm for factoring integers using elliptic curves; it is shown below, or you can run it at http://ideone.com/QEDmMY. Beware that my code is optimized for ...
1
vote
1answer
232 views

Complexity of Pollard's p-1 method

I'm working on the complexity of various integer factorization algorithms and am kind of stuck on the complexity of Pollard's p-1 method. (I'm using Prime Numbers - A Computational Perspective by ...
5
votes
0answers
156 views

Fastest Primality test using $N-1$ Factorization?

If $N-1$ could be factored easily with several small prime factors, then what is the fastest way to check $N$ for primality? Updated I'm aware of Pocklington primility test which is not good for ...
0
votes
1answer
689 views

What is the term for the product of two prime numbers?

Numbers that can be factored down into 2 and only 2 prime numbers, such as: 25 (5 * 5) 9 (3 * 3) 12752041 (3571 * 3571) Is there a mathematical term for these ...
2
votes
1answer
73 views

Factorization, Prime Numbers, and Limits to Our Grasp of Each

I have been fascinated with prime numbers ever since I was very young and actually setup a "Sieve of Eratosthenes" long before I ever knew that something like that existed. As I have gotten older and ...
2
votes
2answers
166 views

Complexity of finding the largest prime factor of a composite number

Is finding the largest prime factor of a number computationally easier than factoring the number into powers of primes?
2
votes
0answers
161 views

How many co-primes are there for a big integer N over a specified interval?

How many co-primes are there for a big integer $N$ over a specified interval ? bounds of $N$ are $[1,10^9]$ and the interval is $[a,b]$ where ($1\leq a\leq b \leq 10 ^{15}$) and there are $100$ ...
6
votes
3answers
10k views

Find the largest prime factor

I just "solved" the third Project Euler problem: The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ? With this on Mathematica: ...
8
votes
1answer
2k views

Pollard-Strassen Algorithm

I'm aware that the Pollard-Strassen algorithm can be used to find all prime factors of $n$ not exceeding $B$ in $O\big(n^{\epsilon} B^{1/2}\big)$ time. This is really useful because I need to find all ...
1
vote
2answers
83 views

Does this sequence have this interesting property relating to the prime factorization of the index?

Define a sequence as $a_0 = 0$ and $a_n$ equals the number of divisors of $n$ (including 1 and $n$) that are greater than $a_{n-1}$. This is sequence A152188 in OEIS, by the way. (For example, the ...
7
votes
1answer
848 views

Even numbers have more factors than odd numbers…

This was an exercise to show that, in a sense, the even numbers have more prime factors than the odds, but--if it's right-- I still have a question. As an heuristic calculation, we could take a large ...
3
votes
2answers
211 views

Find $X$, $a$ : ALL prime factors of $(X^a - 1)/(X - 1) < X$

where $X$ is an odd prime, and $a$ is an odd integer. For example, let $X = 37$, $a = 3$, we get $$\frac{37^3-1}{36} = 3 \times 7 \times 67.$$ When factoring numbers such as this, I've noticed that ...
2
votes
1answer
420 views

Factoring a number $p^a q^b$ knowing its totient

We are given: $n=p^aq^b$ and $\phi(n)$, where $p,q$ are prime numbers. I have to calculate the $a,b,p,q$, possibly using computer for some calculations, but the method is supposed to be symbolically ...
2
votes
1answer
316 views

How to find the factors of numbers around 1e7?

I don't have a maths background but I'm solving problems on the awesome Project Euler .net in JavaScript as programming practice. I don't want to link directly to the question or post it verbatim ...
0
votes
2answers
135 views

What are the specifics and the possible outputs of Pollard's Rho algorithm?

I'm trying to implement a simple prime factorization program (for Project Euler), and want to be able to use Pollard's Rho algorithm. I read the Wikipedia, wolfram|alpha, and planet math explanations ...
31
votes
4answers
1k views

Could G. H. Hardy make a product of two primes so big he couldn't find out which?

This question of course began as a slightly irreverent play on the riddle, "Can God make a stone so big He can't lift it?" Then I wondered about the answer. Is it possible to exhibit a number that is ...
4
votes
4answers
1k views

How can we prove that among positive integers any number can have only one prime factorization?

I have read right from school that prime factorization is unique, but have never found proof for this. Can someone show me the proof?
1
vote
1answer
153 views

Interesting prime factorization function divisibility problem [duplicate]

Possible Duplicate: Is the set of all numbers which divide a specific function of their prime factors, infinite? Let the function $f(n) =(p_1^{a+1}-1)(p_2^{b+1}-1)... $ where $n$ is an ...
1
vote
0answers
94 views

Is there a name for a number whose factors' exponents are all prime?

For instance, 864, whose factorization is 2^5 x 3^3.
1
vote
1answer
194 views

Unique factorization less than 100

How do I approach this problem using unique factorization?... How many numbers are product of (exactly) $3$ distinct primes $< 100$? edit: Just to add to that, How does unique factorization ...
1
vote
0answers
70 views

lower bounds for maximum computing times for integer factorisation

Supposing that n were known to have two prime factors, and that the computer had a database of all the primes $<\sqrt{n}$. Then, unless n is square, one factor would be $<\sqrt{n}$. If an ...
2
votes
1answer
95 views

Factoring short intervals

There are algorithms (e.g., SIQS) that factor individual numbers. For large ranges of numbers, sieving is more efficient: for example, $(x^2,x^2+x)$ can be factored in time roughly linear in $x$. ...
8
votes
4answers
690 views

How to determine in polynomial time if a number is a product of two consecutive primes?

How to determine in polynomial time if a number is a product of two consecutive primes? All I can figure out is that if Cramér's conjecture is true, then we can use the AKS primality test to find ...
2
votes
2answers
133 views

Calculations with liars and sums of prime factors

Suppose you are given a number $n$ and told that the sum of its prime factors is $s$. I'm looking for an efficient algorithm that checks the truth of the statement. Obviously one can simply ...
2
votes
3answers
1k views

About the factors of the product of prime numbers

If a number is a product of unique prime numbers, are the factors of this number the used unique prime numbers ONLY? Example: 6 = 2 x 3, 15 = 3 x 5. But I don't know for large numbers. I will be using ...