Рома Авданин Саша Шень и грибы
Отсюда
http://www.mail-archive.com/cryptography-digest@senator-bedfellow.mit.edu/msg00136.html



From Guiding Troops to Picking Wild Mushrooms.
A surprising new application of GPS technology.
By Sergei Burkov.

>From aiming intercontinental ballistic missiles to picking wild
mushrooms -- such is the evolution path of one once classified defense
technology. A group of Silicon Valley geeks is combining their love of
high tech with their other passion -- hunting wild mushrooms in the pine
groves of Northern California. A group of enthusiast within San
Francisco Mycological Society is going to employ GPS (Global
Positioning System) technology to increase precision of determining
the location of wild mushrooms in the forests.

Until recently, mushroom hunting was virtually unknown in the U.S. In
other part of the world, including Italy, France, and China, it’s
extremely popular. In Russia, it’s a national pass-time, compared in
popularity only to playing ice hockey and drinking vodka. In fact, it were
Russians who first began using GPS technology for hunting
mushrooms in the thick forest surrounding Moscow. Now, Russian
programmers working in Silicon Valley are importing the technology
and share it with their new American colleagues.



Every experienced mushroom hunter knows that the mushrooms grow
in the same place year after year. This is because the mushrooms are
seasonal growths on vast underground structures, called mycelium. If
a picker finds a group of mushrooms one year there are very good
chances that there will be good bounty at the same location the next
year, and year after. Being able to locate the place year later greatly
improves the productivity of the hunter. In Russia, many babushkas
have their secret spots they revisit for decades. They pick lots of
premium mushrooms, to the envy of younger folks who are wandering
in the forest at random, returning home with empty baskets.

It is not easy to find one specific pine tree among thousands or virtually
identical ones in a thick forest. All trees look alike. And it’s harder to
navigate as you step off the trail with its signs and trail blazes. Old
ladies rely on their instincts. Impatient young geeks rely on cutting
edge technology.

With right technology, it works like 1-2-3. Find a good mushroom
(better a bunch of). Determine your position with a GPS device
connected to a Palm Pilot. Enter the coordinates into a database. Go
find next mushroom. Continue. Next year, load the map marked with
last year’s spots into your Pilot, or directly into the GPS device, and go
straight to the best secret spot. To the babushkas envy, the device will
help you find the very same tree you visited a year ago, in minutes.

High tech gives the techno-savvy even sharper edge over the
babushkas. Before the forage, in the comfort of your room, you
examine the map and determine the optimal path. You do not want to
wander too much back and forth, you want to visit your secret spots as
fast as possible.

Here is where the geeks have an edge. The problem of visiting a set of
given spots in minimal time is the well known travelling salesman
problem. It has been studied by thousands of computer scientists,
economists and mathematicians. It is almost as famous as recently
proven Fermat’s last theorem. The exact solution of the travelling
salesman problem is still not found, and many mathematicians believe
will never be, but there are thousands of approximate solutions that
give the paths that are only few percentage points longer than the
minimal ones. For all practical purposes, a good approximate solution
is as good as the absolutely minimal one.

With all this in mind, Alexander Shen and Fedor Sherstyuk, two
Russian outdoor enthusiasts, avid mushroom pickers and GPS buffs
have developed a software product, called Gribnik (Russian for
"mushroom hunter"). The program maintains a data base of the
promising spots and calculates the optimal path in seconds. The
results are superimposed on a local map and downloaded into a Pilot
or directly into a GPS device. The shareware program became so
popular in Moscow that the friends are now working on a commercial
version. An English language version of Gribnik will be available in the
fall of 1999, in time for the season.

The standard accuracy of a typical GPS is about 50 m (150 ft), which is
helpful but does not allow one to pinpoint the mushroom. A differential
GPS which relies on a fixed ground station along with the usual three
satellites could render the 10 cm (4') accuracy. This leads the hunter
straight to the mushroom. To take advantage of such an
unprecedented accuracy the friends climb a toll tree in the middle of
the forest and put a ground station there. Then they decent and search
the surrounding forest.

Unfortunately, even 10 cm precision does not guarantee the
mushroom is there. Even if the timing is right and the mushrooms grow
well there is a chance that somebody has already picked them up.
Knowing this fact in advance will be beneficial to the picker. He would
merely skip the spot and go straight to the next one. Gribnik Pro, a
soupped up version of the program, offers a solution even to this
problem. When one member of a group of hunters picks a mushroom,
or finds that the spot has been cleared by a low tech babushka, he
marks the spot on the map and shares his knowledge with the others.

The sharing has a drawback. If a persons posts the coordinates of the
spot he has just cleared all others become aware of the spot. A good
hunter keeps best spots secret. Messrs. Shen and Sherstyuk founded
a web site where the
users of Gribnik Pro could post the coordinates of their spots in an
encrypted form. (To be more precise, a so-called one-way hash
function of the coordinates is posted on the web.) This way, the
competitors cannot read the coordinates off the web. However, if two
people know about one spot, the program would compare the hash
function values of the coordinates from the data bases of the two
hunters. This allows one hunter to post a note that the spot has been
visited without revealing the coordinates of the spot. Those who also
happen to be aware of the same spot will be able to understand the
message. Others, who have not been to the spot will remain unaware
of it. This yet another example of how, with little help from modern
cryptography, one can eat a cake and still have it. The cryptographic
part of Gribnik was contributed by Roman Avdanin of Invincible Data
Systems, Inc. (http://www.incrypt.com)

What lies ahead? At a press conference on the 1st of April in Moscow
Alexander Shen, Professor at Moscow Center of Continued
Mathematical Education (http://www.mccme.ru), revealed his plans: "We are
going to port the entire Gribnik, including the travelling salesman part,
to Palm Pilot and Windows CE platforms and link it to a cell phone.
This will allow a group of pickers to exchange data about spots in real
time. When a spot is taken the program will remove it from the to-visit
list and recalculate a new optimal path, on the fly. You will receive a
brief phone call and your Palm Pilot will tell you to skip the birch 13 and
proceed straight to the pine 21, across Pereplyujka river, 50 m south
west of an abandoned tiny wooden church and log home, where at
time of Ivan the Terrible a single hermit might have lived and picked his
mushrooms from the same spot."

Sergei Burkov, Ph.D.,
INVINCIBLE DATA SYSTEMS, INC.