Re: Modular Algebra: Find number of elements of a subset modulo n

In article <1164390870.955784.12740@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
Dani Camps <danicamps81@xxxxxxxxx> wrote:
Dear all,

I have the following problem:

Consider this equation modulo n:

ax=b mod n

It is known that if I take "a" and multiply it by a growing constant
x=0, 1, 2 ... and then I do the modulo n operation, I am generating a
soubgroup of Zn, <a>, where the number of elements of this group is
equal to N=lcm(a,n).

No, it isn't that.

Say n=4, a=2. Then lcm(a,n)=4. But the multiples of 2 form a subgroup
of order 2 of Z_4.

Or say n = p is a prime, and a is some number, 1<a<p. Then a generates
all of Z_p, but lcm(a,p) = pa > p.


It is also known that the subgroup generated by "a", has the same
elements than the subgrup generated by "d", <d>, where d=gcd(a,n).

Right. Which means that the subgroup generated by a has order
n/gcd(a,n), and not lcm(a,n) as you claimed above.

Therefore we can express the elements of the subgroup <d>, as "d*i
where i=0...N-1". Let's see an example:

See above. You're wrong about N; you should have N= n/gcd(a,n), not
lcm(a,n).


imagine a=94 and n=36,

Can I just "take" them to be that, rather than "imagine" them? (-:

gcd(94,36) = gcd(22,36) = gcd(22,14) = gcd(8,14) = 2, so the subgroup
generated by a should have order n/gcd(a,n) = 36/2 = 18.

the elements generated by <a> would be:
<a>={0 22 8 30 16 2 24 10 32 18 4
26 12 34 20 6 28 14}

Right; it would be nicer if you used commas...

In this case we would have d=gcd(94,36)=2, then the elements generated
by d would be:
<d>={0 2 4 6 8 10 12 14 16 18 20
22 24 26 28 30 32 34}

We can see how indeed both sets <a>, <d> contain the same elements but
in a different order. My first question is then:

-How to find the permutation that maps the elements of <d> to the
elements of <a>, and the inverse permutation ?

Since d = gcd(a,n), there exist r and s integer such that

d = r*a + s*n.

Therefore, d = r*a (mod n). Thus,
k*d = r*ka (mod n).

Thus, "multiplication by r" gives the desired permutation in one
direction. Find the multiplicative inverse of r modulo n to get the
permutation going the other way.

For example, here you have a = 94, n = 36, d = 2. We have that

2 = 5*94 - 13*36. So r = 5.

Indeed, taking the elements of <a> in order,

<a>={0, 22, 8, 30, 16, 2, 24, 10, 32, 18, 4, 26, 12, 34, 20, 6, 28, 14}

multiplication by 5 modulo 36 yields, in order,

0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34

Now, you can figure out that 1 = (-7)*5 + 1*36, we have that the
multiplicative inverse of 5 modulo 36 is -7 (that is, 29). So the
inverse permutation is multiplication by 29. Indeed, note that

2*29 = 58 = 22 (mod 36), giving you the value of a modulo 36. Etc.


For instance in our example we can see that the permutation that maps
the elements of <d> to the elements of <a> is : i = 5*j mod N, where i
is the index in <a> that maps to the index j in <d>.
How to do it in general ?

Use the extended Euclidean algorithm to write d = r*a +
s*n. Multiplication by r is the map from <a> to <d>. Find the inverse
of r modulo n (you can do it using the Euclidean algorithm again);
multiplication by this inverse gives the map going back.

-And now the issue that I really need to solve, is the following:
Given an intial position in <a> "pos" and a length "m", I can define a
subset of <a>,s_<a>, as the "m" elements of <a> starting from "pos",
in our example with "pos"=2 and "m"=6:

s_<a>={8 30 16 2 24 10}

Then what I need to know is how many elements within this subset,
s_<a>, are below or above a certain threshold. For instance I need to
know how many elements are below 14. In our example:

s_<a> < 14 => {8 2} -> 2 elements.

The problem could be stated as: Find how many elements in the subset
s_<a> are below or above a certain threshold, as a function of
a,n,N,pos and m.

What we can assume is that a>n.

Any idea ?

Not off the top of my head; sorry.



--
======================================================================
"It's not denial. I'm just very selective about
what I accept as reality."
--- Calvin ("Calvin and Hobbes" by Bill Watterson)
======================================================================

Arturo Magidin
magidin-at-member-ams-org

.

Relevant Pages

  • Re: Modular Algebra: Find number of elements of a subset modulo n
    ... Arturo Magidin wrote: ... -How to find the permutation that maps the elements of to the ... Find the multiplicative inverse of r modulo n to get the ... inverse permutation is multiplication by 29. ...
    (sci.math)
  • Re: polynomials over Z_p
    ... fwill define a permutation if and only if there does not ... exist a and b, not congruent modulo p, such that u= -v. ... But in the rest of your explanation I'm ... multiplicative inverse of u modulo p. ...
    (sci.math)
  • Re: polynomials over Z_p
    ... fwill define a permutation if and only if there does not ... exist a and b, not congruent modulo p, such that u= -v. ... But in the rest of your explanation I'm ... multiplicative inverse of u modulo p. ...
    (sci.math)
  • Re: polynomials over Z_p
    ... Suppose that a and b are not congruent modulo p; ... and so we can cancel them modulo p to get ... fwill define a permutation if and only if there does not ...
    (sci.math)
  • Re: quick algorithm for random permutation
    ... This algorithm works great, was easy as pie to implement, ... I'm using the generated permutation of 1...n ... to permute another array of objects. ... However, later on, I have to apply the inverse permutation ...
    (comp.theory)
Quantcast