# Tagged Questions

The tag has no wiki summary.

167 views

188 views

### Algorithm for fast factorization of polynomial over $\mathbb Z$ or over $\mathbb F_p$

I want to fast decompose polynomial over ring of integers (original polynomial has integer coefficients and all of factors have integer coefficients) and also over ring of integers modulo prime ...
217 views

2k views

### Difficulty of factoring a Gaussian integer (compared to factoring its norm)

Given a Gaussian integer $G=a+ib$, with $gcd(a,b)=1$, a well-known strategy for factoring $G$ is to first compute its norm $N(G)=a^2+b^2$, factor the norm and finally recover the correct generator ...
100 views

### counting irreducible factors

In How hard is it to compute the number of prime factors of a given integer? a question was asked on computing number of prime factors of an integer. Suppose we have a polynomial $f(X)\in \Bbb Z[X]$ ...
112 views

91 views

### Efficiently factorize a KKT system with block diagonal upper corner

I have a system resulting from a quadratic energy minimization with linear equality constraints enforced with Lagrange multipliers which has the form: A = \left[\begin{array}{c|c} ...
79 views

### What algebras does the hidden subgroup problem for finite abelian groups apply to?

Shor's algorithm is said to solve the hidden subgroup problem for finite Abelian groups, of which factoring and the discrete logarithm problem for integers belong to. Apparently the HSP for finite ...
172 views

### Given an arbitrary composite odd integer $N$, find two integers $P$ and $Q$ such that $P-Q \neq 1$ and $N=P^2-Q^2$ [closed]

Given an arbitrary composite odd integer $N$, find two integers $P$ and $Q$ such that: $P-Q \neq 1$ and $N=P^2-Q^2$ I am assuming that the best known solution to this problem runs at $O(2^{|N|})$. ...
347 views

### Proving conditions on $(r+s)^2 \mid (4r^4+1)$, related to Pell oblongs

While working on another problem (Solving the quartic equation $r^4 + 4r^3s - 6r^2s^2 - 4rs^3 + s^4 = 1$), I came across a question which seems to be of [semi-] independent interest. Conjecture. If ...
200 views

### Large gaps between consecutive irreducible polynomials with small heights

For a prime gap of length at least $n$, a trivial upper bound for its first occurrence is $N=n!$ or $N=lcm(2,\dots,n)$. A bit better is $N=p_1\cdots p_n$ where $p_k$ is the $k$th prime, as then ...
131 views

### Aurifeuillean factorization with number fields

Basically the question is if number fields can be used in Aurifeuillean factorization. Probably this is easy and the answer is "no". Let $f,g \in \mathbb{Z}[x], a \in \mathbb{N}$. Let $f(x)$ and ...
508 views

### Are there any fast algorithms for factoring integers that don't work by searching for smooth numbers?

All of the fast algorithms that I have seen which factor integers work by searching for smooth numbers. Are there any fast algorithms for factoring integers that don't work by searching for smooth ...
688 views

### The number of distinct prime factors of $n\in\mathbb N$

Let $\omega(n)$ be the number of distinct prime factors of a natural number $n$. Note that $\omega(n)=0\iff n=1$, and that $\omega(24)=\omega(2^3\cdot 3^1)=2\ (\not = 4)$. (For more details, you ...
807 views

### Density of Irreducible Polynomials in $\mathbb{Z}[x]$

Recently I was thinking about some questions concerning $\mathbb{Z}[x]$ and realized that they might be a bit easier if I knew the relative densities of reducible polynomials. Let $P_d$ denote the ...
392 views

### Number of ways to write an integer as a product of irreducibles

Is there any way to tell the number of distinct ways to factor $a\in\mathcal{O}_k$ (up to units, of course) when $k$ is not a PID? A simple investigation in $\mathbb{Q}(\sqrt{-5})$ with integer ring ...
103 views

### Coim factorization of a morphism in a complete well-powered category

In a complete, cocomplete and well-powered category with zero object consider the canonical factorization of a morphism $f=k\circ \mathrm{Coim}(f)$. Does cocomplete+complete+well-powered guarantee ...
398 views

### Using the decomposition $641 = 5^4 + 2^4$ to factor $F_5$

The question in the title arises from a problem in Stewart's "Galois Theory, Third Edition" (and possibly elsewhere) which has been bugging me for a few days since reading it: Problem 19.5 (p. 224) ...
788 views

### $\omega(p^n - 1)$ as $n \rightarrow \infty$

Although I am also interested in the number of distinct prime factors (not counting multiplicity), today I use $\omega(m)$ to denote the number of (positive) prime factors (with multiplicity) of the ...
531 views

### For any prime $p$, is there $C$ such that if $x\ge C$, then all but one integer among $x+1, x+2, \dots, x+p$ has Greatest Prime Factor $> p$

I apologize if this is a naive question about greatest prime factors (gpf). I was thinking about the sequence of integers where $\mathrm{gpf}(x) \le p$ where $p$ is any prime. Clearly, as $x$ ...
157 views

### Collision polynomials

Consider $P_n(x)$ polynomials defined through the recurrence relations $$P_n(x)=2(1-x)P_{n-1}(x)-(1+x)^2P_{n-2}(x),$$ with $P_0(x)=1$ and $P_1(x)=1-3x$. In fact, the explicit solution of these ...
150 views

### Significance behind splitting of (x+y)^7-(x^7+y^7)? [closed]

A quick check via third roots of unity establishes$$(x+y)^7-(x^7+y^7) = 7xy(x+y)(x^2+xy+y^2)^2$$ Some questions: What is the significance of this factorization? Does it have any connection to the ...
157 views

### Elements of low multiplicative order and computing square roots modulo composites

In "On computing factors of cyclotomic polynomials", Richard P. Brent gives the identity $$4 \Phi_n(x) = A_n(x)^2 - (-1)^{(n-1)/2} n B_n(x)^2 \qquad (1)$$ where $n$ is odd squarefree and $A_n,B_n$ ...
1k views

### Seeking Noetherian normal domain with vanishing Picard group but not a UFD

Once again, the question says it all. My motivation is the article on factorization I am writing. I want to explain (as well as to understand!) why for normal Noetherian domains of dimension greater ...
250 views

### Generating 3SAT circuit for Integer factorization example

I read somewhere that 3SAT can be used to solve Integer Factorization. If that is true, could someone teach me a simple example of generating the 3SAT by using a small number? Let's say you are given ...
228 views

### How can an integer be factorized as n*m so that n^m has the highest value. [closed]

Given an integer d, is there a way of finding max(n^m), where d=n*m, except brute-forcing it ? n and m don't have to be primes. For example: The number 12 can be factorized into two factors as: ...
Let $N$ be a positive integer. Thanks to the Miller-Rabin test and the work of Agrawal, Kayal and Saxena, these days people have much much faster algorithms for testing whether $N$ is prime or ...
Background: In the 1700s, Euler solved the Basel Problem, which was to solve $\sum_{n=1}^\infty\frac{1}{n^2}$ in closed-form. Euler showed that it was equal to $\frac{\pi^2}{6}$ by first expressing ...