The tag has no wiki summary.

learn more… | top users | synonyms

2
votes
1answer
447 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
503 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
610 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
244 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
554 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
525 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
617 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
480 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
760 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
498 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
312 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
646 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
752 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$, ...
3
votes
1answer
405 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
993 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 ...