# Re: Question on modular algebra

*From*: "Dani Camps" <danicamps81@xxxxxxxxx>*Date*: 19 Mar 2007 06:56:25 -0700

On Mar 17, 1:12 am, Mike Amling <nos...@xxxxxxxxxx> wrote:

Dani Camps wrote:

On 16 mar, 10:54, "Dani Camps" <danicamp...@xxxxxxxxx> wrote:

On 15 mar, 16:46, Peter Pearson <ppear...@xxxxxxxxxxxxxxx> wrote:

On 14 Mar 2007 08:43:26 -0700, Dani Camps <danicamp...@xxxxxxxxx> wrote:Hi,

[snip]

I have a sequence generated with the following expression[snip]

A(x)=(d + a*x) (mod n)

Where 0<=d<n, and a and n are coprimes, i.e gcd(a,n)=1.

Consider r consecutive values of the sequence A(x)An approximate solution would be simple. Do you need an

starting from 0, so {A(0) ... A(r-1)} where 0<=r<n. What I

want to know is how many values of the subset {A(0)

... A(r-1)} are above my threshold j.

exact solution? Faster than just counting them?

--

To email me, substitute nowhere->spamcop, invalid->net.

What I am looking for is the exact value in a close formula. I need

this in order to proof something, so I am not interested in an

algorithm. Do you have any idea ? An approximation, or better a bound,

can be a starting point.

Best Regards

Dani

Actually what I need to proof is that r/(m-1) is bigger than sth, so I

need a lower bound for r/(m-1). Where r is the lentgh of the sequence,

and m is the number of elements in the sequence {A(0) ... A(r-1)}

above/below the threshold j.

"m is the number ... above/below ..." Well, which is it?

If m is the number of values above the threshold, then for a=1, d=0,

we find the first j values below the threshold j, so r/(m-1) is -r for

1<=r<=j, and the lower bound is no higher than -j.

If m is the number of values below the threshold, then for a=1,

d=j+1, we find the first n-j-1 values above the threshold, so r/(m-1) is

-r for 1<=r<=n-j-1, and the lower bound is no higher than -n+j+1.

Or is the lower bound to be taken over some other domain than all

(a,d,r) combinations?

--Mike Amling

Hi,

I want to show that r/(m-1) is bigger than sth, let's say A. A is not

directly related with (a,d,j,n), that's why I wanted first to find a

lower bound for r/(m-1) as a function of (a,d,j,n), hoping that then I

would be able to compare the expression with A.

Regarding m it should be the number of elements below the threshold,

but I said above/below is because it really does not matter, if

instead of m I find the number of elements above j, lets say b, then m

is simply r-b.

Regards

Dani

.

**References**:**Question on modular algebra***From:*Dani Camps

**Re: Question on modular algebra***From:*Peter Pearson

**Re: Question on modular algebra***From:*Dani Camps

**Re: Question on modular algebra***From:*Dani Camps

**Re: Question on modular algebra***From:*Mike Amling

- Prev by Date:
**Re: Jim Reed's Hagelin Cryptanalysis article** - Next by Date:
**Re: A sort of reverse SAT** - Previous by thread:
**Re: Question on modular algebra** - Next by thread:
**JSH: Sobering invention, surrogate factoring** - Index(es):