For questions about finding factors of e.g. integers or polynomials

learn more… | top users | synonyms

6
votes
1answer
224 views

Factoring some integer in the given interval

Let N be a positive integer. Is there an efficient (i.e. probabilistic polynomial time) algorithm which, on input a sufficiently large N, outputs the full factorization of some integer in the interval ...
4
votes
1answer
133 views

Solve $a^3 + b^3 + c^3 = 6abc$

Find solutions for $a^3 + b^3 + c^3 = 6abc$ in $\mathbb{N}$, such that $gcd(a,b,c) = 1$, except for $(1,2,3)$ and its permutations. Using trial and error I found out that if $a,b,c$ are solution ...
3
votes
1answer
93 views

Find a divisor satisfying a given congruence

Suppose I have a highly composite positive integer $N$ with at least $10^{15}$ divisors for which I know the prime factorization. Given $M$ with $\gcd(M,N)=1$ is there an efficient way to find a ...
3
votes
1answer
85 views

Factorization of integers - why does it suffice to consider squarefree instances?

I sat a lecture where a proposition is proven that states the following: If computation of $(k!)_{k\in\mathbb{N}}$ is "easy", then integer numbers can be factored in non uniform polynomial time. ...
6
votes
0answers
79 views

Is there an easy way to factor polynomials with two variables?

On a recent precal test, I saw a question involving the following expression: $$(x+1)^2-y^2$$ Which factored out into: $$(x+y+1)(x-y+1)$$ This wasn't very hard, considering that it was already ...
5
votes
0answers
150 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
148 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 ...
3
votes
0answers
73 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
0answers
96 views

Why does Lenstra ECM work?

I came across Lenstra ECM algorithm and I wonder why it works. Please refer for simplicity to Wikipedia section Why does the algorithm work I NOT a math expert but I understood first part well enough ...
2
votes
0answers
53 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 ...
2
votes
0answers
66 views

What is the line of thinking to get $[(n^2+3n+1)^2-5n(n+1)^2]$ from $(n^4+n^3+n^2+n+1)$?

There is this one little tiny step along the working that I don't quite understand, but I think it is better if I write the whole problem and solution for clarity. Problem: Factorise $5^{1995}-1$ ...
2
votes
0answers
20 views

Decomposability of a function into two

This is question on the existence of a decomposability of a function $f(v)$ into multiplicative factors $\lambda(v)$ and $g(v)$. The question is non-trivial since the functions $\lambda(v)$ and $g(v)$ ...
2
votes
0answers
90 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 ...
2
votes
0answers
46 views

Different elliptic curves over given $\mathbb{F}_q$ can have different orders?

As the title says: For a given $q \in \mathbb{N}$, in $\mathbb{F}_q$, is it true that different curves on it can have different group orders? I assume yes. Let $q:=5$. Wikipedia gives $9$ points for ...
2
votes
0answers
152 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$ ...
2
votes
0answers
88 views

Factors of a polynomial in several variables

Fix an embedding of $\overline{\mathbb{Q}}$ into $\mathbb{C}$. Suppose you have a polynomial in several variables, with algebraic coefficients: $P\in \overline{\mathbb{Q}}[z_1, \ldots, z_n]$. Also ...
1
vote
0answers
30 views

Proof for maximal ideals in $\mathbb{Z}[x]$

I have been trying to prove the following theorem: Every maximal ideal in $\mathbb{Z}[x]$ has the form $(p, f(x))$ where p is prime integer and f is primitive integer polynomial that is irreducible ...
1
vote
0answers
9 views

By what factor do winning chances increase based on total value?

Say I am entering 24/7 in endless sweepstakes, contests, giveaways, drawings, etc. Assuming each one I enter has no less than 1 in 1,000 chances, but no more than 1 in 1 million (and I enter at least ...
1
vote
0answers
23 views

On number of different factorizations over integers of a number field

Let $K$ be a finite field extension of the rational numbers and let $\mathcal{O}_K$ denote its ring of integers. If a rational integer $n$ factors into two distinct ways into irreducible elements in ...
1
vote
0answers
15 views

Which factors determine whether a set of variables are suitable for factor analysis?

Which factors determine whether a set of variables are suitable for factor analysis? I am looking as much for an explanation of the question as a tentative answer to it. So grateful for any help on ...
1
vote
0answers
51 views

How are the general skills for complete factorization of arbitrary homogeneous order polynomials in $\mathbb{C}$?

How are the general skills for complete factorization of arbitrary homogeneous order polynomials in $\mathbb{C}$ ? For example: $1.$ $a^2+b^2+c^2$ $2.$ $a^2+b^2-c^2$ $3.$ $a^2+b^2+c^2+d^2$ $4.$ ...
1
vote
0answers
129 views

Find the set of cyclotomic cosets of q modulo n

Calculating finite field and factoring $x^n - 1$ over $GF(q)$ first step is to calculate cyclotomic cosets. For example : For $n=9,q=2$ $C_1=\{1,2,4,8,7,5\} = C_4 = C_8 = C_7 = C_5$ $C_3=\{3,6\} ...
1
vote
0answers
233 views

Finding irreducible polynomials and factorization

Need some explanation and checking if my thinking on the solution is correct for the assignment given below: (In these problems you may use without proof which polynomials of degree 2 and 3 are ...
1
vote
0answers
37 views

Given a cubic $f(x)$ with specified negative real roots $-a,-b,-c$, what happens when we search for solutions to $f(x)=d$?

Noting Roots of a Certain type of Cubic Equation, what if we have the following simpler form for real $d$: $$(x+a)(x+b)(x+c)=d\tag{1}$$ (With $a,b,c\in \mathbb R^+$.) Clearly, depending on $d$, the ...
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 ...
1
vote
0answers
45 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
98 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 ...
1
vote
0answers
389 views

Factorization of cyclic polynomial

Factorize $a(b^2-c^2)+b(c^2-a^2)+c(a^2-b^2)$ Since this is a cyclic polynomial therefore factors are also cyclic : $f(a) = a(b^2-c^2)+b(c^2-a^2)+c(a^2-b^2)$ $f(b) = b(b^2-c^2)+b(c^2-b^2)+c(b^2-b^2) ...
1
vote
0answers
99 views

What is the condition for a polynomial to be factorizable in linear real factors?

I have a polynomial $p_a(x,y)= x^2F(a)+y^2G(a)-xH(a)-I(a)$ where $F(a)$, $G(a)$, $H(a)$ and $I(a)$ some real fuctions of $a$ are. Which conditions must satisfy $a$ so that I can factorize the ...
1
vote
0answers
71 views

Understanding of Pollard rho factorization

I am trying to better understand the ideas and intuition behind the Pollard Rho factorization algorithms. Given an $x_0$ and an irreducibe polynomial we can create a sequence from the recursive ...
1
vote
0answers
136 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 ...
1
vote
0answers
91 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
0answers
241 views

Factoring multivariate polynomials

If I have a multivariate polynomial $P[X_1,\dots,X_n]\in \mathbb{R}[X_1,\dots, X_n]$, is there a polynomial time algorithm to factor the polynomial into irreducible polynomials $\in ...
1
vote
0answers
69 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 ...
0
votes
0answers
23 views

Proof for uniqueness for ideal multiplication

I am across the following question here: The uniqueness of a special maximal ideal factorization Let R be a domain, and let I be an ideal that is a product of distinct maximal ideals in two ways, ...
0
votes
0answers
13 views

Finding number of integral solutions

How many integral solutions are possible for $w,x,y,z$ given that $$w^{p_1} x^{p_2} y^{p_3}z^{p_4}= N$$, where N is a natural number? For example, number of solutions for $x^3y^3z^1 = 360$. My notes ...
0
votes
0answers
30 views

Is this factorization true for all $n$ in the natural numbers

I need to know if $x-a=(x^{\frac{n}3}-a^{\frac{n}3})(x^{\frac{n+1}3}+a^{\frac{n}3} x^{\frac{n}3}+a^{\frac{n+1}3})$ Is true. I know its true for $n=1$, is it true for all natural numbers though?
0
votes
0answers
24 views

Bounding parameters for Shor's Algorithm

I am working on a program for classical implementation of Shor's algorithm to factor products of small primes, just to better understand how it works. The program will conduct order finding using ...
0
votes
0answers
71 views

RSA - How can I calculate $\phi$ from $n$ in small prime numbers?

Hello I would like to learn if there is a way to calculate the $\phi$ from small prime numbers. There is a way even slow like brute-force or something else like a formula to calculate $\phi$. For ...
0
votes
0answers
58 views

The annihilator of finitely generated modules over PID

Let $R$ be a principal ideal domain. Let $M$ be a finitely generated $R$-module. Suppose there exists prime ideal $p$ and integer $i$ such that $p^i=\operatorname{Ann}(M)$. Then prove: (1) there ...
0
votes
0answers
33 views

Polynomial factorization over an infinite field - is there an algorithm

In my previous questioned I asked how do I factor a polynomial, and I gave an easy example of a polynomial of degree 2. But now I have another question I need to solve. I need to factor ...
0
votes
0answers
261 views

New method derived out of Fermat's factorization method

Let us take two examples: a) $N=943=41*23=(\frac{41+23}{2})^2-(\frac{41-23}{2})^2$ but if we take $B=\frac{N+1}{4}$ then we can represent it as $B={x}^2-({y}^2+y)$ and in our case: ...
0
votes
0answers
60 views

Factoring: solving for 'x' in a power equation.

Is it possible to solve for b in the following? $$g={t(b-1)\over(b^k-1)}$$ I have attempted this by hand and on a leading online calculator, but have been unable ...
0
votes
0answers
59 views

What does the general factorization of a multivariable polynomial look like?

Any polynomial $p$ in the ring $\mathbb{Z}[x]$ factors into an expression of the form $z_0(x - z_1) \dots (x - z_k)$, with $z_0, \dots, z_k \in \bar{\mathbb{Z}}$ (the algebraic closure of ...
0
votes
0answers
39 views

How to find per second of failure?

I want someone to help me solve this. An attacker is hitting the right username after 80% failed attempts after every five minutes. I got failure %, and time. What is the fail ratio how can i ...
0
votes
0answers
63 views

Factoring from order finding?

It appears that if you have a finite field, F_p, and you can factor the order of the field, p-1, then you can easily construct an arbitrary nth root of unity in F_p and also check that it be primitive ...
0
votes
0answers
147 views

Factoring polynomials $f(g(x))$ over extension fields.

This question is a variation on another one : related question Let $f(x)$ and $g(x)$ be polynomials with integer coefficients and discriminant of $f(x)$ > discriminant of $g(x)$ , which are ...
0
votes
0answers
148 views

Approximations for the number of divisors of an integer

Given an integer $n$, I want to know the asymptotic order of: a. the number of distinct prime factors b. the number of non-distinct prime factors c. the number of distinct divisors d. the number ...
0
votes
0answers
59 views

What is this special type of factor called?

I'm wondering if there's a special term for the following: The (special factor) of a number $x$ is a pair of numbers that multiply to give $x$ but has the smallest difference compared to other ...
0
votes
0answers
54 views

Figuring $x$ where $x = \max \{ \operatorname{round}(7),0 \}$

I'm a software developer and do very little with math but I have been called upon to incorporate a math function into my app I'm developing. I'm stumped as to how to figure $x$ where $x = \max \{ ...