The tag has no wiki summary.

learn more… | top users | synonyms

2
votes
0answers
90 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]$ ...
2
votes
1answer
106 views

Which nonnegative matrices have exact nonnegative matrix factors of smaller dimensionality?

The nonnegative matrix $V = \left( \begin{array}{cc} 1 & 1 \\ 1 & 1 \end{array} \right)$ has nonnegative matrix factors $W = \left( \begin{array}{c} 1 \\ 1 \end{array} \right)$ and $H = ...
1
vote
0answers
86 views

Puzzling CAS-detected factorization by cyclotomic polynomials [closed]

If one factorizes by CAS the expression $$x^{\frac{m(m+1)}{2}}\prod_{k=1}^m(x^k+(\frac{1}{x})^k)$$ a puzzling perfect factorization seems to be possible for all natural values of $m$. E.g. for ...
3
votes
0answers
78 views

More 3-connected cubic graphs with all 2-factors of same cycle type?

The setup is as in this question: Let $G$ be a 3-connected cubic graph. If all 2-factors of $G$ are isomorphic (as graphs), i.e. all have the same partition $\pi$ as cycle type, we'll say that $G$ is ...
6
votes
2answers
221 views

Cubic graphs whose 2-factors all have the same cycle type

Let $G$ be a bridgeless cubic graph. I am interested in such graphs where all 2-factors are isomorphic (as graphs), i.e. have the same partition as cycle type. We'll say that this partition is ...
3
votes
2answers
339 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
132 views

Bounded domain matrix factorization

Assume we're trying to find $A\in [-1,1]^{n\times d}, B\in [-1,1]^{m\times d}$, from an observed matrix $C\in [-d,d]^{n\times m}$, where $C=AB^T$. The goal is to return $\widehat A, \widehat B$ such ...
4
votes
0answers
78 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: \begin{equation} A = \left[\begin{array}{c|c} ...
0
votes
0answers
69 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 ...
3
votes
3answers
371 views

Distinct primitive factorizations over integers of number fields

I am curious about the following. Let $K$ be a number field. For any $a \in \mathcal{O}_K$ in its ring of integers, let $N(a)$ be zero if there exist elements $b, c \in \mathcal{O}_K \setminus ...
-6
votes
1answer
154 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|})$. ...
0
votes
1answer
120 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 ...
8
votes
2answers
532 views

runs of consecutive non squarefree integers

This question gained no attention at Math SE. Call a sequence of $k$ consecutive naturals squary if each one of them is divided by a square > 1. The Chinese Remainder theorem trivially guarantees us ...
6
votes
4answers
452 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 ...
4
votes
1answer
413 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 ...
7
votes
0answers
224 views

Do the coefficients of these irreducible polynomials always become periodic?

Fix $n\in\mathbb N$ and a starting polynomial (or seed) $p_n=a_0+a_1x+\dots+a_nx^n$ with $a_k\in\mathbb Z\ \forall k$ and $a_0a_n\ne0$. Define $p_{n+1},p_{n+2},\dots$ recursively by $p_r = ...
5
votes
1answer
190 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 ...
7
votes
2answers
339 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 ...
3
votes
1answer
341 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 ...
3
votes
0answers
97 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 ...
6
votes
1answer
375 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) ...
18
votes
1answer
1k 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 ...
5
votes
2answers
150 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 ...
3
votes
0answers
142 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 ...
7
votes
3answers
762 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 ...
2
votes
0answers
146 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$ ...
0
votes
2answers
212 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 ...
0
votes
1answer
214 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: ...
0
votes
1answer
766 views

Can infinite polynomials be expressed as a product of its linear factors?

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 ...
2
votes
2answers
254 views

Factorization of antisymmetric bounded holomorphic functions

A basic principle in complex function theory is that one can split off zeros of holomorphic functions in a similar way as for polynomials: If $f$ is holomorphic near $0$ and $f(0) = 0$, then $f(z) = ...
16
votes
11answers
3k views

Fastest way to factor integers < 2^60

I've been running a search for Mordell curves of rank >=8 for about 12 months and have identified approximately 280,000 curves in our archivable range, amongst many millions that aren't. For this ...
5
votes
0answers
434 views

Optimal Gear Trains

Suppose you need to slow down a turning motor so that a gear turns at an angular velocity $\frac{a}{b}$ of that of the motor shaft, where $a$ and $b$ are natural numbers. For example, this set of ...
2
votes
3answers
510 views

Groups of Rational Points on Gaussian Circles

Let a gaussian circle $C_R$ be any circle defined by the equation: $$x^2+y^2 = R, (x,y) \in \mathbb{R}^2$$, where $R$ is the norm of a gaussian integer ($R=a^2+b^2, (a,b) \in \mathbb{Z}^2$). IF $R$ ...
1
vote
3answers
511 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$ ...
2
votes
3answers
2k views

Algorithm for detecting prime powers

While reading Peter Shor's paper Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, I came across the following quote: "This scheme will thus work as ...
11
votes
3answers
978 views

What is known about the polynomial factorization of power series?

Some power series factorize; $1+\sum_{n=1}^\infty x^n=\prod_{n=1}^\infty (1+x^{2^n})$ and $1+\sum_{n=1}^\infty x^{2n}/(2n+1)!=\prod_{x=1}^\infty (1+x^2/n^2\pi^2)$ for example; while others do ...
11
votes
2answers
712 views

Saying things rapidly about integer factorisations

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 ...
5
votes
1answer
408 views

Divisibility and factorization in rings that are not integral domains

In my course notes for an undergraduate course "Algebra I", I wrote at the point when I'm introducing the notion of divisibility in rings (in a section on unique factorization): We want to study ...
1
vote
2answers
527 views

find the minimum difference between the factors of a number

Given a number c, what is the smartest way to find |x - y| such that x * y =c and |x - y| is minimum
9
votes
5answers
1k views

Polynomials all of whose roots are rational

I have two questions about the class of integer-coefficient polynomials all of whose roots are rational. I asked this at MSE, but it attracted little interest (perhaps because it is not interesting!) ...
2
votes
5answers
397 views

Factoring a certain quartic mod primes

Let $h(x)=x^4+12x^3+14x^2-12x+1$, and let $p>5$ be a prime. I want to show $h(x)$ factors into 2 quadratics mod $p$ if $p \equiv 9,11$ mod 20, while $h(x)$ factors mod $p$ into 4 linear factors if ...
12
votes
1answer
412 views

Is the ring of quaternionic polynomials factorial?

Denote by $\mathbb{H}[x_1,\dots,x_n]$ the ring of polynomials in $n$ variables with quaternionic coefficients, where the variables commute with each other and with the coefficients. Two polynomials ...
-2
votes
1answer
439 views

Are these polynomials irreducible over ring Z of integers ?

Is it true that polynomials of the form : $ f(x)= x^n+x^{n-1}+...+x^{k+1}+ax^k+ax^{k-1}+...a$ where $gcd(n+1,k+1)=1$ and $ a\in \mathbb{Z^{+}} $ are irreducible over ring $\mathbb{Z} $ of ...
1
vote
2answers
373 views

Finding a divisor of a number under a constraint

Given 2 positive integers $n, l$ with $ l \leq n$, I am looking for a way to find the largest divisor $d$ of $n$, such as $d \leq l$. Assume $n$ has too many divisors for an exhaustive search. Thanks ...
12
votes
1answer
2k views

Evidence for integer factorization is in $P$

Peter Sarnak believes that integer factorization is in $P$. It is a well-known open problem in TCS to identify the real complexity class of integer factorization. Take a look at this link for Peter ...
1
vote
2answers
1k views

Finding the greatest (smallest) factor of a number smaller (greater) than another number

Instead of iterating through all the possible numbers, is there a better way to find the greatest factor of a number $n$, such that it is less than $m$ ($m$ < $n$). Similarly how does one find the ...
2
votes
1answer
441 views

Factoring and Index Calculus and duality between DL and factoring via compuational problems made easy through them

If factoring is in $P$ (with a blazing fast polynomial time in $P$), would it affect the index calculus algorithm used for Discrete Log calculation in any serious way? Other connections $1.)$ ...
6
votes
1answer
492 views

Is this pleasing polynomial irreducible?

Let: $f(x)=x^n+2x^{n-1}+3x^{n-2}+4x^{n-3}+\ldots + (n-1)x^2+nx+(n+1)$. Is $f(x)$ irreducible? In light of the answers to this question, I now know that this is true when $n+1$ is prime. What about ...
7
votes
2answers
608 views

Factoring some integer in the given interval

I'm posting this question here (rather than on CSTheory) since it seems to require much more knowledge about number theory than algorithms. Let N be a positive integer. Is there an efficient (i.e. ...
2
votes
1answer
241 views

10 factors for x^2 coefficient in quadratic sieve?

I wrote a quadratic sieve and I tried plugging in all the same parameters as the wikipedia article says msieve uses: http://en.wikipedia.org/wiki/Quadratic_sieve#Parameters_from_realistic_example It ...