Scaling in Modular Inverse problem with very large integers

[amzoti]

Hi All,

a theoretical or numerical answer would suffice - and I am having
brain freeze at the moment!

I have the following - with all numbers positive integers.

x = a number

n = modulus

k = the number of "groupings by 7" of hex digits of n

b = 2^28

Below the (^-) represents modular inverse.

c = (b^(-k) * x) (mod n).

Here is an example - "all" numbers below are in hex.

x = 2fd1beb3394c940dca86f8184410

n = ac93debd410439

k = 2 (since there are 14/7 = 2 hex digit groups in n)

b = 10000000

c = (b^(-k) * x) (mod n) = b0058886c2756

Okay - so my question is if there is any way to change my x and n with
k >= 256 so that c remains the same value (in other words - to scale x
and n (which affects k) in such a way as to keep the same value of c)?

This would mean that n would have at least 256 * 7 hex digits = 1792
hex digits. x can change in any way including staying the same to make
this work.

Any ideas if this is possible?

Thanks for any inputs!

~A

[Pubkeybreaker]

On Oct 3, 4:28�pm, amzoti <amz...@gmail.com> wrote:
> Hi All,

> c = (b^(-k) * x) (mod n) = b0058886c2756
>
> Okay - so my question is if there is any way to change my x and n with
> k >= 256 so that c remains the same value (in other words - to scale x

Huh??? Just solve for x. It is trivial. Just keep
c,b, & k constant.

x = c * b^k mod n

[amzoti]

Trouble is - k is not a constant.

k is dependent on the size of n and I need to change n which also
changes k.

Keeping c and b constant is okay.

[amzoti]

On Oct 3, 2:40 pm, Pubkeybreaker <pubkeybrea...@aol.com> wrote:

Okay - sorry - like I said - I was having brain freeze!

Got it - thanks!

~A

[Mensanator]

On Oct 3, 3:28 pm, amzoti <amz...@gmail.com> wrote:
> Hi All,
>
> a theoretical or numerical answer would suffice - and I am having
> brain freeze at the moment!
>
> I have the following - with all numbers positive integers.
>
> x = a number
>
> n = modulus
>
> k = the number of "groupings by 7" of hex digits of n
>
> b = 2^28
>
> Below the (^-) represents modular inverse.
>
> c = (b^(-k) * x) (mod n).
>
> Here is an example - "all" numbers below are in hex.
>
> x = 2fd1beb3394c940dca86f8184410
>
> n = ac93debd410439
>
> k = 2 (since there are 14/7 = 2 hex digit groups in n)
>
> b = 10000000
>
> c = (b^(-k) * x) (mod n) = b0058886c2756

I'm not clear on this. The modular inverse function I have is
defined as

invert(...)
invert(x,m): returns the inverse of x modulo m, i.e., that y
such that x*y==1 modulo m, or 0 if no such y exists.

So, when you say b^(-k) are you asking for y such that b*y==1 mod k?

There is no such y if b is 10000000 and k is 2,
so I must be interpreting it wrong.

[Pubkeybreaker]

On Oct 3, 6:16 pm, Mensanator <mensana...@aol.com> wrote:
> On Oct 3, 3:28 pm, amzoti <amz...@gmail.com> wrote:
>

> I'm not clear on this. The modular inverse function I have is
> defined as
>
> invert(...)
>     invert(x,m): returns the inverse of x modulo m, i.e., that y
>     such that x*y==1 modulo m, or 0 if no such y exists.
>
> So, when you say b^(-k) are you asking for y such that b*y==1 mod k?

The notation *is* clear. b^(-k) is clearly 1/(b^k) mod n. WTP?????