The tag has no wiki summary.

learn more… | top users | synonyms

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
404 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 ...
13
votes
1answer
427 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
454 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
387 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
3k 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 ...
2
votes
3answers
2k 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
450 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.)$ ...
7
votes
1answer
510 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
614 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
246 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 ...
5
votes
3answers
2k views

Reduction from factoring to solving Pell equation

The paper Polynomial-Time Quantum Algorithms for Pell's Equation and the Principal Ideal Problem claims There are reductions from factoring to solving Pell’s equation, and from solving Pell’s ...
3
votes
0answers
564 views

Least Prime Factor in a sequence of 2n consecutive integers

I was thinking about consecutive integers and I wondered if anyone had done work exploring whether a sequence of $2n$ consecutive integers (i.e. 101,102,103,...,100+2n) always contains at least one ...
16
votes
1answer
1k views

Factoring Integers using Complex Integrals

Suppose $n$ is an integer and we wish to factor it. As a special case we have $n = pq$ with $p,q$ distinct primes. The problem: factoring $n$ via complex analysis tools Background I have been ...
5
votes
0answers
534 views

Is integer factorization harder than RSA ($n=pq$) factorization? [closed]

This is a repost. I could not get a precise answer on math.SE and cstheory.SE Let FACT denote the integer factoring problem: given $n \in \mathbb{N},$ find primes $p_i \in \mathbb{N},$ and integers ...
2
votes
1answer
629 views

What are the chances of finding a small factor?

EDIT 2011.05.09 Thanks to Junkie and Tapio Rajala for checking on me. While most of the candidates referred to below have small factors, the "large" small factors I list below are incorrect. Also, ...
2
votes
2answers
498 views

when does a regular graph have a 1-factorization?

Is there a sufficient condition for a regular graph to have a 1-factorization (i.e. being able to pack all of its edges into disjoint perfect matchings, and excluding one vertex if the number of ...
0
votes
1answer
130 views

“locally” factoring subgroups of Lie groups

I'm not really a math person, and apologize if the question here is too simple. I've ended up with the following type of question for a few Lie groups, but state it for SO(n). I start with a subgroup ...
7
votes
3answers
780 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 ...
2
votes
2answers
503 views

Second stage of elliptic curve factorization via random walk/Pollard's rho in constant (or low) memory?

The second stage of elliptic curve factorization has the drawback of large memory usage. Let $n=pq$, $E(\mathbb{Z}/n\mathbb{Z})$ is elliptic curve and $P$ point on $E(\mathbb{Z}/n\mathbb{Z})$. On ...
1
vote
1answer
316 views

Cartesian factorization of a finite set of n-tuples

I'm interested in factoring a finite set of $n$-tuples as the Cartesian product of two "factor sets", of which the first factor is itself the Cartesian product of some of the set's projection images, ...
2
votes
1answer
649 views

A subring question (revised)

Hello, Let $K/{\mathbb Q}$ be a finite extension which is not necessarily Galois, and ${\mathcal O}$ be the ring of integers of $K$. Let $p$ be a prime in ${\mathbb Q}$ and let $p {\mathcal ...
7
votes
4answers
2k views

Consecutive numbers with n prime factors

Let $P(m,n)$ mean that there is a number, $M$, such that starting with $M$ there are $m$ consecutive numbers each having exactly $n$ distinct prime factors. Is it obvious that $P(m,n)$ is true for ...
0
votes
2answers
755 views

Prime factorization theory

Firstly, let me divulge. I've been doing a lot of research on the summation of two coprime numbers and unfortunately have failed to come up with the properties I'm seeking; it is my hope that someone ...
7
votes
1answer
199 views

Adding a multiple of the Identity to a LU factorized matrix

Suppose a square, dense, symmetric matrix $A$ has been factorized into $L$ and $U$ components by performing a LU decomposition. Now let $B = A+\lambda I$. Is there any way to efficiently compute the ...
6
votes
2answers
4k views

Fast trace of inverse of a square matrix

Which would be the most efficient way (in computational time) to compute tr(inv(H)), where H is a (dense) square matrix? In my particular problem I also have a LU decomposition of H already ...
0
votes
1answer
159 views

QR factorization: How to get decreasing r_ii

Hi, I'm attempting to implement a QR factorization with column pivoting so that the returned R matrix has decreasing diagonal elements (that is, $r_{i,i} \leq r_{i-1,i-1}$ for all $i\geq 2$). ...
3
votes
0answers
155 views

Pulling out factors in a Noetherian Domain

Let $R$ be a Noetherian domain (not-necessarily commutative), and let $S$ be a Noetherian subring of $R$. An element $r\in R$ is left $S$-irreducible if, for any $s\in S$ and $r' \in R$ with $sr'=r$, ...
4
votes
1answer
412 views

Factorization in the Wiener algebra on the unit disc.

Consider the Banach algebra $W^+=\ell^1(\mathbb{Z}^+)$, viewed upon as the analytic functions $f$ on the unit disc $\mathbb{D}$ such that $$\|f\|=\sum_{k\ge0}|a_k|<\infty$$ where $$f(z)=\sum ...
14
votes
2answers
1k views

How divisible is the average integer?

I don't know any number theory, so excuse me if the following notions have names that I'm not using. For a positive natural number $n\in{\mathbb N}_{\geq 1}$, define $Log(n)\in{\mathbb N}$ to be ...
4
votes
2answers
994 views

Factoring and solving trinomials

Has the problem of factoring (over the rationals) the general trinomial $ax^n+bx^k+c$ with $a,b,c\in\mathbb{Z}$, $n,k\in\mathbb{N}, n>k>1$ been solved? By solved I mean a classification theorem ...
12
votes
6answers
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 ...