0
$\begingroup$

Is there a system that has modular inverses for non prime mods?

Ultimately what I am trying to do is design a hash function that given a list of n outputs (mod m) and inputs (large arbitrary integers), can efficiently compute some salt such that the hash function would map all inputs to the desired outputs. I also want the entropy of the this salt to be as small as possible. So on average, $\log salt = \log m^n$.

One idea that works perfectly for prime mods is to convert the salt to base m, and take the dot product with the input base m. Then take this value mod m. The salt can be found by solving a system of linear equations mod m. But to do this requires an inverse which only exist for prime m's.

In more mathy notation:

  • salt can be turned into a vector, x by converting it to base m.
  • inputs can form a matrix "A" (let's call a specific row lowercase "a") by turning each input into a sequence mod m (either by repeatedly hashing it or if it is large enough converting to base m). Match its length to x.
  • let y = the outputs
  • hash function = $a \cdot x\mod m$
  • to solve for x, just solve, $Ax=y\mod m$

There may be other ideas to achieve this goal. Also I'm not sure if this is the correct place to ask this question, other ideas would be in crypto.

The purpose of this algorithm is to design a more space efficient "perfect hashing" method for read only values and I think if it can be solved would deserve a paper to be written, credit would be due to any answers!

$\endgroup$
7
  • $\begingroup$ Plenty of non-prime moduli have invertible elements, it just won't be true that all non-zero classes will have inverses. What is it that you really want? $\endgroup$
    – Randall
    Commented Oct 19, 2021 at 18:17
  • $\begingroup$ Also, if $n$ factors non-trivially as $ab$, then working mod $n$ will have $a$ as a noninvertible element. $\endgroup$
    – Randall
    Commented Oct 19, 2021 at 18:18
  • $\begingroup$ @Randall I do need it to work for all non zero to guarantee that Ax=y can be solved. What I really want is some numbering system that has inverses mod m, or some other method altogether to solve this non prime issue. An example of the former: 1 -> i, 2 -> 1, 3 -> 1+i, 4-> 2, etc. but this system won't work because 4 is still not invertible - this just demonstrates what I mean by an alternate system (polynomials is another idea but that requires prime bases too I believe). $\endgroup$
    – Darren Smith
    Commented Oct 19, 2021 at 18:23
  • $\begingroup$ That won't happen modulo a non-prime, per my comment. There will always be non-zero invertibles. The value $n - \varphi(n)$ will tell you have "bad" it is. $\endgroup$
    – Randall
    Commented Oct 19, 2021 at 18:25
  • 1
    $\begingroup$ The key term is "group." That's what you want to be working in. $\endgroup$
    – Randall
    Commented Oct 19, 2021 at 18:33

1 Answer 1

Reset to default
0
$\begingroup$

It cannot be done, but an abelian group can be constructed of any size by prime factorization, which should have the desired properties.

Note that I had tried this method, but then the difficulty became numbering values in a way that satisfied the entropy requirement. I'll try again with that.

$\endgroup$
2
  • $\begingroup$ actually this isn't quite right as it needs a second operation similar to addition (I'm out of my element here) $\endgroup$
    – Darren Smith
    Commented Oct 19, 2021 at 21:55
  • 1
    $\begingroup$ Many of these things can be altered to work with matrices in some non-abelian group, which also gets interesting. If you have/want vector data, matrices are a natural place to look. $\endgroup$
    – Randall
    Commented Oct 19, 2021 at 23:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .