Wikipedia:Reference desk/Archives/Mathematics/2014 April 29

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

April 29

One-way function with certain properties?

Consider some one-way function F(X) that satisfies both F(A + B) = F(A) + F(B) and F(A − B) = F(A) − F(B). Are these properties useful for anything? -Sebastian Garth (talk) 03:44, 29 April 2014 (UTC)

This is an additive map (also called an additive function, in the first sense given in the lede of this article). A special, but particularly useful case of this is a linear map (also called a linear function). Whenever subtraction is a binary operation (particularly, that it is defined for all values of its inputs, as it would be for integers and real numbers), your first property implies the second, so it would be unnecessary to list it separately. —Quondum 04:39, 29 April 2014 (UTC)

On second reading, it seems improbable that you'd find a one-way function with this property, if the function's domain and codomain are in the same set, and the addition operation is the same. Of course, there are examples where the domain and codomain are different, for example F(x) = g^x (which also can also be written xg, if the group operation is written as "+"), where g is a generator of some abelian group (with x an integer). This has extensive application in public key cryptography. —Quondum 04:55, 29 April 2014 (UTC)

Quondum, do you mean a function with this property, but without any other reasonable property (in particular, not bijective) with domain and range being the same is hard to find? YohanN7 (talk) 13:28, 29 April 2014 (UTC)

I think what he's saying is if the domain of a function and its codomain are both contained in a certain set, and if the '+' and '-' symbols mean the same thing on both sides of the OP's equations, then any linear map is trivial to invert, and thus is not a one-way function. I could be misunderstanding Quondum, and there might be tricks I'm not aware of, but non-esoteric or non-exotic linear maps are usually easy to invert. SemanticMantis (talk) 14:56, 29 April 2014 (UTC)

While being interesting, the question of whether a function is easy to invert might be besides the topic. Then again, it might not be. The OP asks if they are useful. Functions whose existence relies, for instance, on the axiom of choice are probably not useful in any sense of the word. But their mere existence (and abundance!) is interesting in every sense of the word. YohanN7 (talk) 15:11, 29 April 2014 (UTC)

Isn't "hard to invert" (for some practical definition of "hard") a necessary feature of a one-way function though? I thought that was the heart of the matter. Surely, if you can use the axiom of choice to define a linear map that is nearly impossible to invert, that would be very interesting, though perhaps of little practical use :) SemanticMantis (talk) 15:23, 29 April 2014 (UTC)

My interpretation is with SemanticMantis's here. Actually, every additive map is Z-linear, so linearity is maybe not so interesting. Not being bijective is also not necessarily interesting, since this includes every linear map with a nontrivial kernel. In any event, functions with the properties listed by the OP (additivity and one-wayness) are precisely the properties exploited by, elliptic curve cryptography, digital signatures, key agreement protocols etc. So I'd say the answer to the OP's question is an unequivocal "yes". —Quondum 16:08, 29 April 2014 (UTC)

Oops, I've managed to miss completely that One-way function is part of the OP question. (I blue-linked it in the title so I wont make the same mistake again.) Please just disregard what I have written here if it appears strange. It was written under other premises. YohanN7 (talk) 16:27, 29 April 2014 (UTC)

Heh-heh – you needn't feel alone. As you may glean from my first post, I initially did the same. —Quondum 16:51, 29 April 2014 (UTC)

So then how could this could be used to create, say, a public key protocol? -Sebastian Garth (talk) 17:00, 29 April 2014 (UTC)

As an example, the ECC algorithm is based upon a one-way function that maps integers to "points". There is an addition operator for each, with a homomorphism from the integers to points. This satisfies your description. Given two points and one integer that maps to the one point, you can subtract the points, but you cannot determine what integer to add to the first integer so that the sum maps to the second point. Multiplication of a point by an integer to produce a point is defined by repeated addition. Pretty much every primitive building block in public key cryptography uses essentially this or similar properties. I can't give you a lecture here, but you should be able to learn quite a bit from the articles that I linked, and articles that those link to. —Quondum 18:51, 29 April 2014 (UTC)

Okay, thank you! -Sebastian Garth (talk) 18:58, 29 April 2014 (UTC)

You have to do something a bit more than just add the results to get a one way function. If F(1)=b then F(A) will be Ab with the rule given so we just need to divide by b to give the value of A. But see Homomorphic encryption for how people are dealing with this sort of thing. Dmcq (talk) 11:09, 30 April 2014 (UTC)

Divide by b? When F is a one-way function, this is equivalent to finding a discrete logarithm. —Quondum 00:28, 1 May 2014 (UTC)

Enter recurring decimal into calculator

Can a scientific calculator be expected to have a function to allow me to enter 4.6 where the 6 is recurring? I know I could enter 4+(6/9) but I was wondering whether there was an alternative to that. My model is Sharp EL-506V. — Preceding unsigned comment added by 129.215.47.59 (talk) 11:16, 29 April 2014 (UTC)

I've spent a couple of minutes starting at a Google Images picture of that calculator and I can't see a button for it, I'm afraid. I couldn't say for sure that it's not there, though; hopefully somebody else could confirm that for you. If it helps, I own a Casio fx-83GT PLUS (...Actually, I own six of them...) and there's an icon of a square with a dot above it which can be used for recurring decmials. JaeDyWolf ~ Baka-San (talk) 12:44, 29 April 2014 (UTC)

Well, any recurring decimal is equivalent to a fraction. At least some scientific calculators allow you to enter mixed numbers, i.e. whole number and fraction. On my HP calculator you can type 4.6.9 to mean 4+6/9 (which, of course, is equivalent to 4.6 recurring). But it's just a shorthand for directly typing 4.66666666667, as the calculator stores only 12 significant digits. If you want a calculator that can store non-integers in fraction (or recurring decimal) form to full precision, that's another matter. --50.100.193.30 (talk) 04:29, 30 April 2014 (UTC)

My elderly Casio fx-115M can handle rationals with up to three digits in each field and eight digits in all: 999 98/999 or 99 998/999. (If the result of a rational operation exceeds that format, it falls back to floating point, with ten digits.) —Tamfang (talk) 06:28, 30 April 2014 (UTC)

If you don't already know this, any recurring decimal 0.abcdabcd... may be written (like your 6/9) as ${\frac {abcd}{10^{n}-1}}$ (multiplied by another negative power of 10 in cases like $0.00142857142857\dots =10^{-2}{\frac {142857}{999999}}$), which makes your method more useful because more general. Many calculators could be trivially programmed to interpret input like repeating(p,n,o) as $10^{-o}{\frac {p}{10^{n}-1}}$ (so that repeating(8.1,54,3,2)=8.10054054…), but it's clumsy because you have to specify the period (3) and the offset (1) of the repetition. --Tardis (talk) 00:21, 1 May 2014 (UTC)

For every x^n, is there a

Hello Wikipedians.

I am not a mathematical person. I did however wonder at the bus today: For every expression of x^y = z, perhaps y 1,2...n - is there an expression of ax^by = z? Like the way 3^2 = 9 and 3^3 = 27, you could have 1.5*3^2*b = 9 and 1.5*3^3*b = 27. (Or just as well: ax^by = cz.

I don't know if this has any significance. I suspect that if there is an 'a' and 'b' that you can cram in there, they're going to be rather special numbers rather than normal whole numbers. Thank you in advance for any help. 83.108.57.148 (talk) 19:10, 29 April 2014 (UTC)

OP here, forgot to finish the full subject. I seem to remember you shouldn't adjust those, so there we are I guess. 83.108.57.148 (talk) 19:11, 29 April 2014 (UTC)

Sure, in fact there are infinitely many a,b that will work. Determining if or how you can get a and b to be integers is much more difficult and subtle (e.g. Diophantine equations). But let's just look at the algebra. x,y are constants.

Then, if we assume $x^{y}=z$, we seek to find a, b such that $ax^{by}=z$. So, take logarithms of each side, and use properties of logarithms to isolate b. $ax^{by}=z\rightarrow x^{by}=z/a\rightarrow \log(x^{by})=log({z/a})$

Then, pull the exponent down, you get $by\cdot \log(x)=log(z/a)\rightarrow b={\frac {\log(z/a)}{y\cdot \log(x)}}$.

So, for any (positive real number) a you pick for the right hand side, you can calculate a b (using the known values of x,y,z) that will satisfy the original equation. Make sense? SemanticMantis (talk) 21:15, 29 April 2014 (UTC)

Ah, a diophantine equation. Brilliant! Thank you for that. 83.108.57.148 (talk) 07:18, 30 April 2014 (UTC)

You're welcome, glad I could help! Seriously though, Diophantine equations are hard (even for experts in math who don't know much number theory, like me). The best way to start would be to get an introductory book on number theory. I recommend any book published by Dover, they tend to be decent-to-high quality, and rather inexpensive too! Here's one I found searching google books for /Dover number theory/ [1]. SemanticMantis (talk) 16:39, 30 April 2014 (UTC)

Possible # Swipe Passwords for my phone.

On my phone, one security option is to swipe (without removing the finger from the screen) a pattern on a three by three pattern of dots. There must be at least 4 dots in the pattern. If that was only limitation, then the number of possible swipe passwords would be (for 9 through 4 dots) 9! + 9! + 9!/2! + 9!/3!+ 9!/4! + 9!/5!.

BUT it will not allow you to avoid a center dot when going from one side to another of it. So for example, the following sequences (numbering the dots 1-2-3 across the top, 4-5-6 across the middle, 7-8-9 along the bottom) are not legal 1-3-6-2 since it couldn't get from 1 to 3 without picking up the 2. OTOH, if the center dot of the three has already been used, you can cross, so 2-6-3-1 *is* a legal sequence. (Similarly going from 9 to 3 picks up 6 and from 3 to 7 picks up 5, etc) How many legal sequences are there?Naraht (talk) 20:21, 29 April 2014 (UTC)

The last bit makes it a little complicated. Without that "skip over an already used number", the answer would be the number of Self-avoiding walks of length >3, on a 3x3 integer lattice. SemanticMantis (talk) 21:20, 29 April 2014 (UTC)

The fact that the path can go from 2-6 or even 2-9 (though you have to be pretty exact to do a knights move) means that the SAW concept doesn't seem to work.Naraht (talk) 21:28, 29 April 2014 (UTC)

Right, that's why I said "without" that rule. Still, computing the number for length 9>L>3 SAW will be a good exercise, and give a decent lower bound. SemanticMantis (talk) 22:22, 29 April 2014 (UTC)

And by computing, you mean having a computer actually run all of the possibilities, right? I can't find any formula...

I think you can calculate such a thing using careful combinatorics and maybe some graph theory. This paper uses analytic methods, but seems to only work with infinite lattices [2]. This paper introduces an algorithm for counting SAW, and I suspect there should be a way to restrict to the simple 3X3 case that you're interested in [3]. In this case, I think you can work it out by hand. Use some arguments from symmetry. Say we just want to count the length 4 walks. First, count all the walks starting at 1. Then that number should be the same for those walks starting at 7,9,3-- the corners. Similarly, the number of walks starting at 2 should be the same as 3,6,8. The walks at 5 only contribute once. You can probably keep track of all of them with a tree_(mathematics) structure, either on paper, or on a computer. SemanticMantis (talk) 19:37, 30 April 2014 (UTC)

• Actually, someone may have found the right answer here [4], I don't have time to read through it carefully. SemanticMantis (talk) 19:43, 30 April 2014 (UTC)

I agree that each of the lengths can be split into 4*starts at corner+4*starts at center edge+starts at center with additional symmetry splits.

The way he describes the situation would allow 1-3-2-6, but I don't know how, that wouldn't seem to work on phones like that, but I'll contribute to that page.Naraht (talk) 15:49, 1 May 2014 (UTC)