The factorization tag has no wiki summary.

**11**

votes

**2**answers

748 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

**1**answer

446 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

**2**answers

564 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

**5**answers

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

**5**answers

406 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

**1**answer

429 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

**1**answer

455 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

**2**answers

394 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

**1**answer

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 ...

**2**

votes

**3**answers

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

**1**answer

454 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.)$ ...

**8**

votes

**1**answer

517 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

**2**answers

615 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

**1**answer

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

**3**answers

1k 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

**0**answers

569 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

**1**answer

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

**0**answers

540 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

**1**answer

632 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

**2**answers

510 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

**1**answer

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 ...

**8**

votes

**3**answers

794 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

**2**answers

516 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

**1**answer

319 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

**1**answer

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

**4**answers

1k 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

**2**answers

756 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

**1**answer

200 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

**2**answers

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

**1**answer

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

**0**answers

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

**1**answer

416 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

**2**answers

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

**2**answers

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

**6**answers

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 ...