Tagged Questions
13
votes
2answers
107 views
Simplifying $\sqrt{\underbrace{11\dots1}_{2n\ 1's}-\underbrace{22\dots2}_{n\ 2's}}$
How do I simplify:
$$\sqrt{\underbrace{11\dots1}_{2n\ 1's}-\underbrace{22\dots2}_{n\ 2's}}$$
Should I use modulos or should I factor them? Or any I suppose to use combinatorics? Any one have a ...
1
vote
4answers
70 views
I cannot find the last factor of this expression?
I'm supposed to factor $x^8-y^8$ (the exponents are 8 for both if it is too difficult to see) as completely as possible. It is easy to factor this to $(x+y)(x-y)(x^2+y^2)(x^4+y^4)$. However, the book ...
3
votes
1answer
36 views
Factors of non-square
How do you solve to find how many of the positive factors of a number, say 36,000,000, are not perfect square? I know how to do this manually, which took me forever, but I want to be able to solve ...
2
votes
2answers
74 views
Is there any known algorithm for factoring the fractional components of a binomial?
For a binomial such as $\binom {15} {6}=\frac{15\times14\times13\times12\times11\times10}{6\times5\times4\times3\times2\times1}$, it seems that it always divides evenly into an integer, and I ...
0
votes
1answer
226 views
Let $N$ = $11^2 \times 13^4 \times 17^6$. How many positive factors of $N^2$ are less than $N$ but not a factor of $N$?
Let $N$ = $11^2 \times 13^4 \times 17^6$. How many positive factors of $N^2$ are less than $N$ but not a factor of $N$?
$Approach$:
$N$=$11^2$.$13^4$.$17^6$
$N^2$=$11^4$.$13^8$.$17^{12}$
This ...
1
vote
0answers
39 views
Integer factorization using discrete logarithms
I'm reading up on RSA and attacks on it. At the end of one section of the notes, it asks (without giving an answer) whether or not integer factorization is easy given an oracle which computes discrete ...
1
vote
0answers
66 views
Prime factors of a random number
Let $r$ be a uniformly random integer between $1$ and $N$, for some large enough $N$ (i.e., I'm only interested in the asymptotics).
What is the expected largest prime factor of $r$? Is there a good ...
0
votes
1answer
72 views
Integer Factoring Algorithm Speeds
Given $N=pq$, would $\frac{p-1}{2}$ steps be fast compared with extant factoring methods?
0
votes
1answer
23 views
Distinct-degree factorization
I'm trying to understand distinct-degree factorization from Wikipedia.
I'm trying the algorithm on paper with $q=9$ and $f(x) = (x+4)(x+5) = x^2+2 \in F_{q}$.
We start with $i=1$. I calculate $g = ...
1
vote
1answer
36 views
probability of a number not having factors below n?
I want to know the probability that a number is not divisible by any prime smaller than or equal to n. ie, I find a big number, I trial division it up to 300000 and don't find any factors. I want to ...
3
votes
1answer
79 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 ...
4
votes
0answers
128 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 ...
5
votes
0answers
112 views
Carmichael number factoring
The task I'm faced with is to implement a poly-time algorithm that finds a nontrivial factor of a Carmichael number. Many resources on the web state that this is easy, however without further ...
4
votes
2answers
146 views
Are Euclid numbers squarefree?
Are Euclid numbers squarefree ?
An Euclid number is by definition a Primorial number + 1.
See http://mathworld.wolfram.com/Primorial.html.
In notation the $n$ th Euclid number is written as $E_n = ...
0
votes
3answers
112 views
Reducible polynomial + integer = Reducible polynomial?
Reducible polynomial + integer = Reducible polynomial ?
As the title says.
More specific :
For every integer $n$, does there exist a pair of polynomials $p(x)$ and $q(x)$ such that:
...
0
votes
2answers
107 views
Finding total number of divisors which divide 2 given numbers [duplicate]
Possible Duplicate:
Number of common divisors between two given numbers
I need to find the total number of divisors which divide both the numbers lets say N and M.
Actually I tried to think ...
2
votes
0answers
115 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$ ...
7
votes
1answer
862 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 ...
3
votes
1answer
119 views
Roots of rational equation with multiple variables?
Let's say we have a rational polynomial in $k$ variables. We are only interested in rational solutions. If $k = 1$, name the variables ${x}$, if $k = 2$, name them ${x,y}$.
For $k = 1$, it can be ...
1
vote
2answers
67 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 ...
0
votes
1answer
199 views
Calculating powers of 2 on a 2D grid without factoring.
Consider the following 2D infinitely large grid where the dots represent infinity:
...
2
votes
2answers
174 views
Determine the number of factors for extremely large numbers.
An offshoot from a related question, is there a way to determine the number of possible factors (odd, even, prime, etc.) for extremely large integers without actually factoring them?
Even an ...
2
votes
3answers
212 views
Factoring extremely large integers.
The question is about factoring extremely large integers but you can have a look at this question to see the context if it helps. Please note that I am not very familiar with mathematical notation so ...
1
vote
0answers
129 views
A special factorization
Suppose that monic polynomial $f(x)\in\Bbb Z[x]$ such that for all $m\in\Bbb Z$, $m>1$, there's no integers $\langle r,r_1,\ldots,r_m\rangle$ such that $f(r)=f(r_1)\cdots f(r_m)$. Is there any ...
3
votes
1answer
129 views
Dixon's random squares algorithm: a step in the proof of its subexp. running time
I am currently working to understand Dixon's running time proof of his subexp integer factorization algorithm (random squares).
But unfortunately I can not follow him at a certain point in his work. ...
3
votes
2answers
173 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 ...
5
votes
1answer
248 views
Smallest number with a given number of factors
From my rather rudimentary explorations of this fascinating problem, I believe it to be a layered and rewarding subject for investigation.
My question, essentially, is: How do you find the smallest ...
0
votes
0answers
77 views
public key crypto
Okay, i have basic knowledge of public key crypto and factoring but:
assume i have LOTS of high value sites I want to attack, lets say banks. Each has a public key pq to crack
assume I gather all ...
2
votes
1answer
317 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 ...
25
votes
4answers
738 views
Fermat's Last Theorem and Kummer's Objection
In 1847 Lamé had announced that he had proven Fermat's Last Theorem. This "proof" was based on the unique factorization in $\mathbb{Z}[e^{2\pi i/p}]$. However, Kummer, proved that when $p=23$ we do ...
4
votes
1answer
297 views
A theorem about prime divisors of generalized Fermat numbers?
A theorem of Édouard Lucas related to the Fermat numbers states that :
Any prime divisor $p$ of $F_n=2^{2^n}+1$ is of the form $p=k\cdot 2^{n+2}+1$ whenever $n$ is greater than one.
Does anyone ...
4
votes
1answer
152 views
Is an algebraic formula for the number of cyclic compositions of n known?
From Wikipedia:
In January 2011, it was announced that Ono and Jan Hendrik Bruinier, of the Technische Universität Darmstadt, had developed a finite, algebraic formula determining the value of p(n) ...
2
votes
2answers
266 views
Number of factors less than a number
I need to find the number of factors of a large number $n^2$ that are less than $n$. Supposing I can find the prime factorization, it is simple to find the total number of factors as a combinatorial ...
4
votes
1answer
286 views
Is it possible to efficiently factor a semiprime given a bit-permutation relating the factors?
Is it possible to efficiently factor a semiprime given a bit-permutation relating the factors? For example, suppose we have $n = p * q = 167653$; in this case, $p = 359 = 101100111_2$ and $q = 467 = ...
2
votes
1answer
87 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
474 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
3answers
252 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 ...
0
votes
2answers
388 views
Factoring Multiple Variable Polynomials
This is in relation to a problem dealing with the three-dimensional analogue of Pell's Equation. I would like to factor
$ x^3+Dy^3+D^2z^3-3Dxyz $ into $\frac{1}{2}(x+Dy+D^2y)$ and another factor.
I ...
