2
votes
0answers
20 views

Finding coefficients of the min polynomial of an $n\times n$

Given an $n\times n$ matrix, for ease assume this matrix is over the $F_m$. What we know about min poly is the the non-zero components of the min polynomial for this case, ie if there is $x^2$, or ...
1
vote
2answers
40 views

Factorising after adding a square

I have been thinking about it for quite some time but am unable to find an answer. Let $a,b,c,d,e$ be any distinct natural numbers. Will the relation : $(x-a)(x-b)+c^2=(x-d)(x-e)$ ever hold? I am ...
1
vote
1answer
30 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 ...
5
votes
1answer
105 views

Is 292229292292 the longest 29-smooth number made of 2's and 9's?

Is 292229292292 the longest 29-smooth number made of 2's and 9's? The factorization is $2^2 7^8*19*23*29$. Is there a general way to find other numbers of this sort without resorting to brute force ...
2
votes
1answer
84 views

Degrees of factors of polynomial $f(x)=x^q-(ax^2+bx+c)\in \mathbb{F}_q[x]$

I’m facing the problem of factoring polynomials of type $f(x)=x^q-(ax^2+bx+c)\in \mathbb{F}_q[x]$ and the degrees of factors seem to be quite special. For example, according to my experimental results ...
0
votes
1answer
16 views

Find subset of rows whose entries sum to an even number in each column

I am trying to implement Fermat factorization with factor bases. The textbook suggests using row-reduction to find a linearly dependent set of rows. How does one go about finding such a linearly ...
1
vote
1answer
44 views

Efficient factorization of numbers with unique prime factors

I need a factorization algorithm for numbers of the form $n = p_{1}p_{2}\cdots p_{k}$ with $p_i \neq p_j$ for $i \neq j$ and $p_j \in \{p : p \mbox{ is a prime and } p \leq P_s\}$, where $P_s$ is the ...
-2
votes
3answers
131 views

An intutive way to think about odd and even numbers. [closed]

What is an intuitive way to think about odd and even numbers? And about divisibility also...
1
vote
1answer
106 views

Sums and differences of distinct factors

Given $k, n \in \mathbb{N}$, let $\tau_{k}(n)$ denote the $k$th positive factor of $n$ in strictly increasing order. For example, $\tau_{1}(6) = 1; \tau_{2}(6) = 2; \tau_{3}(6) = 3; \tau_{4}(6) = 6$. ...
4
votes
1answer
50 views

Complexity of factoring non-squarefree numbers

Consider the two numbers $N_1=p_1\cdot p_2$ and $N_2=p_1^2\cdot p_2$, where $p_1$ and $p_2$ are primes. Is there any factoring algorithm that can factor $N_2$ faster than the asymptotically fastest ...
1
vote
1answer
87 views

If discriminant of f is a perfect square, then we can factor f into linear factors

Let $f$ be a binary quadratic form with integer coeficients, $f(x,y)=ax^2+bxy+cy^2$. I'm trying to prove that if $d=b^2-4ac$ is a perfect square $d=k^2$, then we can factor ...
4
votes
1answer
79 views

Which positive integers can be written in the following form?

I was investigating a generalisation of this problem and found that it reduced to finding where the expression $$\frac{p(p+2m+1)}{2}$$ is an integer, where $p\ge 2$ and $m \ge 0$. Since exactly one of ...
1
vote
1answer
33 views

Factors of $x^n+1$ over $\mathbb{Z}[x]$

Is there any equivalent to $x^n-1 = \prod\limits_{d|n} \phi_d$ where $\phi_d$ is the $d$th cyclotomic polynomial but for $x^n+1$? Even better, can we generalize any further?
-2
votes
2answers
59 views

Common divisor of natural number sequence [closed]

For all natural numbers $n$, the products $(n+2)(n+3)(2n+5)$ will always share what common divisor ?
2
votes
1answer
70 views

How many integral solutions of $a,\ b,\ c$ are there such that $2^a \cdot 3^b + 9 = c^2 $

How many integral solutions of $a,\ b,\ c$ are there such that $$2^a \cdot 3^b + 9 = c^2.$$ we can get that $$2^a \cdot3^b = (c-3)(c+3) $$ we can make cases if $b \ge 2$ then $c=3k$ then ...
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 ...
2
votes
1answer
36 views

Find the smallest value of $n$ so that the greater potency of $5$ which divides $n!$ is $5^{84}$. What are the other numbers that enjoy this property?

Find the smallest value of $n$ so that the greater potency of $5$ which divides $n!$ is $5^{84}$. What are the other numbers that enjoy this property? I thought I would put together an equation ...
2
votes
1answer
82 views

Find the prime factor decomposition of $100!$ and determine how many zeros terminates the representation of that number.

Find the prime factor decomposition of $100!$ and determine how many zeros terminates the representation of that number. Actually, I know a way to solve this, but even if it is very large and ...
1
vote
2answers
31 views

If $N$ is not a power of a prime, why does 1 have -1 as a root modulo $N$?

If integer $N$ is not a power of a prime, it is the product of two coprime integer numbers greater than 1. As a consequence of the Chinese remainder theorem, the number 1 has at least four ...
3
votes
1answer
66 views

Finding $a_n$ such that $x^n+a_1x^{n-1}+\cdots+a_{n-1}+a_n$ cannot be factored when $a_1,\cdots,a_{n-1}$ given

Let $n\ge 4\in\mathbb N$. Suppose that $a_1,a_2,\cdots,a_{n-1}$ are given integers. Then, here is my question. Question : Is the following true for any $(a_1,a_2,\cdots,a_{n-1})$ ? There ...
0
votes
2answers
79 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 ...
1
vote
1answer
88 views

Number of divisors of a number

Is there any trick to find the number of divisors of any number? For e.g., a quick way to tell the number of divisors of 987655432 (chosen randomly)? EDIT: And it has to be done without prime ...
3
votes
0answers
83 views

Symmetry in the Sum of Factors

The factors of 72 are 1,2,3,4,6,8,9,12,18,24,36,72. The factors can be organized as such $$m=1,2,3,4,6,8$$ $$n=72,36,24,18,12,9$$ Knowing the symmetric properties and that the 12 factors exist. Pair ...
3
votes
2answers
176 views

Why does prime factorization hold in the set of integers of the form $4k+1$?

I want to prove that in the set $$ S = \{4k+1 : k\text{ is a positive integer}\}$$ (i.e. $S = \{1, 5, 9, 16, \dots \}$) unique prime factorization holds. How do I do that? Edit: a prime in this ...
2
votes
1answer
80 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 ...
1
vote
0answers
60 views

Parametric Equation solving over integers

I have a question on my mind I am trying to solve. However I am stuck at a point. If you could help, I would be very pleased. $$\frac {x_2y_2z_2}{x_2y_2+y_2z_2+x_2z_2}=\frac ...
3
votes
1answer
238 views

Solve $x+y+z = x^3 + y^3 + z^3 = 8$ in $\mathbb{Z}$

Solve $x+y+z = x^3 + y^3 + z^3 = 8$ in $\mathbb{Z}$ First I tried to transform this equation, substituting $x = 8-y-z$. So I end up with: $$x^3 + y^3 + z^3 = 8$$ $$(8-y-z)^3 + y^3 + z^3 = 8$$ ...
1
vote
1answer
84 views

How many divisors of $n$ are less than or equal to $m$?

Can I calc it in less than $O(\sqrt{n})$ time?
2
votes
0answers
96 views

Quadratic Diophantine Equations in Polynomial Time

Considering the problem of finding lattice points $(x_1, x_2 ... x_n)$ that satisfy a quadratic law: $F(x_1, x_2... x_n) = 0$ such that $F(x_1, x_2... x_n)$ is a second degree polynomial It is ...
1
vote
1answer
274 views

Patterns in $GF(2)$ Polynomial division.

I am testing Prime polynomials in $GF(2)$ and have noticed a pattern that I hope will help. There's a calculator here if you want to familiarise yourself with polynomials over $GF(2)$. I am testing ...
2
votes
2answers
293 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$$ ...
5
votes
1answer
55 views

Balanced factors

A non-square number cannot be factored to two identical factors. However, not all non-squares are equal: some of them can be factored to relatively close factors (for example, $6=2*3$), while others ...
14
votes
2answers
158 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
77 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
45 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
1answer
94 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 ...
1
vote
1answer
332 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
51 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
101 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
132 views

Integer Factoring Algorithm Speeds

Given $N=pq$, would $\frac{p-1}{2}$ steps be fast compared with extant factoring methods?
0
votes
1answer
32 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
64 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 ...
4
votes
1answer
144 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 ...
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 ...
5
votes
0answers
154 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
183 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
148 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
179 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
159 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$ ...
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 ...